链表笔试题

最近在刷面试题，以下是对链表面试题的总结：

1.从尾部到头部打印链表；

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。   主要有三种方法：  （1）创建一个数组，遍历链表时，将链表值存入数组当中，遍历结束后，从尾部到头部遍历；时间复杂度o(n)，空间复杂度o(n);  （2）创建一个栈，遍历链表，将链表值压入栈中，遍历结束后，将栈中值压出；时间复杂度o(n)，空间复杂度o(n);  （3）采用递归的方式，将最先的数据最后打印；时间复杂度o(n)，空间复杂度o(1);     注：方式(3)在链表比较长时，会出现方法次数执行太多，无法执行成功的情况；     2.链表反转； 给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

主要有3种办法：

　　(1)创建一个栈，遍历链表，将链表值压入栈中，遍历结束后，将栈中的值压出，重新构建新链表；时间复杂度o(n)，空间复杂度o(n);

    （2)遍历链表，在遍历链表时，将链表进行反转；时间复杂度o(n)，空间复杂度o(1);

　  (3)采用递归的方式，进行链表反转；