当前位置：首页 > news >正文

【LeetCode刷题日记】：反转链表（面试基础考察）

news 2026/6/5 9:33:04

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

反转链表：

题目背景：LeetCode206

给你单链表的头节点head，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]输出：[2,1]
示例 3：
输入：head = []输出：[]
提示：
链表中节点的数目范围是[0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

双指针解法：

/ 双指针 class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; ListNode temp = null; while (cur != null) { temp = cur.next;// 保存下一个节点 cur.next = prev; prev = cur; cur = temp; } return prev; } }

题目解析：
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:
我们只需要改变链表的next指针指向：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。不然会导致数据丢失，
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。
我们把cur的指向改变，指向pre，然后我们分别继续移动这两个指针，cur的位置给pre，temp的位置给cur，都相当于是向后移动一次
为什么先移动pre，而不是先移动cur，如果是先移动cur，那么cur的值就被temp覆盖了，pre的位置就改变不了了。

递归解法：

// 递归 class Solution { public ListNode reverseList(ListNode head) { return reverse(null, head); } private ListNode reverse(ListNode prev, ListNode cur) { if (cur == null) { return prev; } ListNode temp = null; temp = cur.next;// 先保存下一个节点 cur.next = prev;// 反转 // 更新prev、cur位置 // prev = cur; // cur = temp; return reverse(cur, temp); } }

解法解析：

递归的逻辑就是双指针的逻辑，，只是写起来的代码更简单些，

在这里我们定义了两个方法，为什么需要两个方法，因为我们要实现递归，需要传递两个参数pre cur，但是题目只给出了一个head，因此reverseList(head)负责启动递归，里面调用reverse(null, head)，真正递归逻辑在reverse(prev, cur)里。

具体流程：

假设原链表：
plaintext
1 → 2 → 3 → 4 → 5 → null

初始调用
reverseList(head);
进入：
reverse(null, 1);
此时：
plaintext
prev = null cur = 1
第 1 层递归：reverse (null, 1)
temp = cur.next =2
cur.next = prev →1 → null
递归调用：reverse(1, 2)
链表现在：
plaintext
null ← 1 2 → 3 → 4 → 5 → null
第 2 层递归：reverse (1, 2)
temp = 3
cur.next = 1 →2 → 1
调用：reverse(2, 3)
plaintext
null ← 1 ← 2 3 → 4 → 5 → null
第 3 层递归：reverse (2, 3)
temp = 4
3 → 2
调用：reverse(3,4)
plaintext
null ← 1 ← 2 ← 3 4 →5 →null
第 4 层递归：reverse (3,4)
temp =5
4→3
调用：reverse(4,5)
第 5 层递归：reverse (4,5)
temp = null
5→4
调用：reverse(5, null)
plaintext
null ←1 ←2 ←3 ←4 ←5
最后一层：cur == null，开始返回
java
运行
if (cur == null) return prev;
这里 prev 是5
然后一层层返回 5 → 最终回到 reverseList
返回 5，链表反转完成！