剑指24. 反转链表 LeetCode 206. Reverse Linked List

题目：

输入一个链表，反转链表后，输出新链表的表头。

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

2026.10.29

又时隔四年了连反转链表都不会了……看了思路才写出来，但还是比较straightforward的，就是需要用prev, curr两个指针一个个小心遍历， 老实连接链表就行，没啥坑。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }

递归依旧不会，只能死记硬背理解了。返回条件倒是写的出来，然后如果不返回的话那就把当前head后面的部分反转好再回来处理head，于是head后面的部分反转好的newHead就是reverseList(head.next)。这个newHead一直都是链表的最后一个节点不变，只是它后面一直需要接上新的元素，which is递归那层的head，所以就是把head接到它原来的next后面，就是head.next.next = head，就把head后面这串链表的尾巴接好了。然后需要设置head.next = null来防止链表形成环。

G老师的总结很到位：

你可以把：

ListNode newHead = reverseList(head.next);

理解成一句话：

「我不负责反转后面的链表，我相信递归调用会帮我把后面的链表反转好，并把反转后的头节点告诉我。」

记住这个原则：修改链表指针时，不仅要建立需要的新连接，也要考虑旧连接是否需要断开。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }

2022.12.19

给想复杂了……还用了dummyHead，然后发现dummyHead一会儿成环了一会儿多了个0……才意识到根本不需要dummyHead……以及时隔两年，还是不会写递归……

2020.10.13 Java

差点没给写出来，吓得我以为我连反转链表都不会了。看了下自己新写的代码比以前的要简洁多了，有进步。对比了一下solutions居然除了变量名temp它起的是tempNext以外完全一毛一样，惊呆。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.

Memory Usage: 38.7 MB, less than 6.72% of Java online submissions for Reverse Linked List.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } }

还是不会写递归，唉。知道了思路也在head.next.next=head那里卡住了。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.

Memory Usage: 39.1 MB, less than 6.72% of Java online submissions for Reverse Linked List.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; } }

这道题没有什么特殊的技巧，就是普普通通地做就好了，也是一道非常经典的题，面试高频题。链表的题首先要考虑给出的头节点为空的情况，直接返回NULL。反转链表这个要格外注意不要把链表给断了，因此我们设置三个指针，分别指向当前节点curr、前一节点prev和后一节点next。在while循环中遍历整个链表，小心翼翼地将curr的next设为prev，并把prev和curr向后挪动一个，直到curr的next为空时达到了链表的尾部，把最后的curr设为反转链表的头节点：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead) { return NULL; } ListNode* prev = NULL; ListNode* curr = pHead; ListNode* new_head = NULL; while (curr) { ListNode* next = curr->next; if (!next) { new_head = curr; } curr->next = prev; prev = curr; curr = next; } return new_head; } };

另外一种递归方法，我理解了好久才搞明白，其实还是比较难想的。首先递归基是当参数中的pHead为空或者pHead->next为空时，就返回pHead，作为反转链表的头节点。接下来通过递归调用这个函数，把递归返回的结果（其实仔细看会发现每次返回的都是原链表的最后一个节点，也就是新链表的头）存起来，然后把当前指向的节点的下一个节点的next设为它自己（这就把指针反过来了），再把当前节点的next设为空，方便下一次设置next（毕竟当前节点在下一次就是前面那句提到的“当前节点的下一节点了），最后返回的就是之前存起来的新链表的头。画了个图：

代码如下：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead || !pHead->next) { return pHead; } ListNode* pReversedNode = ReverseList(pHead->next); pHead->next->next = pHead; pHead->next = NULL; return pReversedNode; } };