动画：面试如何轻松反转链表？
16lz
2021-01-22
题目
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
例如：
问题分析
反转链表，首先想到的是让最后一个结点作为头结点，第一个结点作为尾结点指向 null。
如果我们把指针反方向改变，就可以轻松完成整个链表的反转。
说到改变指针，我们有两个方式，第一种是从前到后改变指针，第二种是从后往前改变指针。从前往后代表迭代方式，从后往前是递归的方式，这个不难理解，直接上动画。
动画实现
递归法
迭代法
解题思路
迭代法
从前到后开始反转，我们需要三个指针，第一个指针指向当前头结点 head，第二个指针指向第二个节点 curP（当前结点）,第三个指针为保存下一个节点的临时节点 temp。
1、反转顺序为，先保存下一节点。
2、然后让当前结点的指向前一节点。
3、最后移动当前结点到下一结点。（head 头节点一开始初始化指向 null）。
4、重复该循环。
递归法
递归法只不过换了一个顺序，先递进去，然后在执行以上反转操作。
1、让当前结点的下一节点的下一节点指向当前结点。
2、当前节点的下一结点指向 null，直到递归完毕，完成反转。
代码实现
javaScript
//& 反转链表 - 递归实现var reverseList = function(curP) { if(curP == null || curP.next == null) return curP; var tail = reverseList(curP.next) curP.next.next = curP curP.next = null return tail;};//& 反转链表 — 迭代实现var reverseList = function(head) { if(head == null || head.next == null) return head; var curP = head.next head.next = null var temp = null while(curP !== null){ temp = curP.next curP.next = head head = curP curP = temp } return head;} java
//& 反转链表 - 迭代实现class Solution { public ListNode reverseList(ListNode head) { if(head == null) return null; ListNode pre = null; ListNode curP= head; while(curP != null){ ListNode temp = curP.next; curP.next = pre; pre = curP; curP = temp; } return pre; }}//& 反转链表 — 递归实现class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode tail = reverseList(head.next); head.next.next = head; head.next = null; return tail; }}python
//& 反转链表 - 迭代实现class Solution: def ReverseList(self, pHead): if not pHead or not pHead.next: return pHead last = None while pHead: tmp = pHead.next pHead.next = last last = pHead pHead = tmp return last//& 反转链表 — 递归实现class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head: return None if not head.next: return head headNode = self.reverseList(head.next) head.next.next = head head.next = None return headNode测试用例
输入空的头结点(null)
输入一个节点的链表
- 输入多个节点的链表