链表专题(二)：乾坤大挪移——「反转链表」

场景想象：你是一队寻宝探险队的队长，队员们排成一列，每个人都把手搭在下一个人的肩膀上（1 -> 2 -> 3）。 现在命令来了：“全体向后转！”

• 每个人都要松开搭在前面人肩膀上的手。

• 每个人都要转身，把手搭在原本在自己后面那个人的肩膀上。

• 原来的队长（头结点）变成了队尾，原来的最后一名变成了新队长。

核心痛点：链表是单向的，指针只能从前指到后。 如果我们想反转，就必须断开当前的指针cur.next，让它指向它的前一个节点pre。 但是！一旦我们断开了cur.next，我们就失去了去往下一个节点的路径。 所以，我们需要三个指针来配合这次“大挪移”。

力扣 206. 反转链表

https://leetcode.cn/problems/reverse-linked-list/

题目分析：

• 输入：链表的头节点head。

• 目标：反转链表。

• 输出：反转后的新头节点。

例子：1 -> 2 -> 3 -> 4 -> 5 -> NULL

• 结果：5 -> 4 -> 3 -> 2 -> 1 -> NULL

核心思维：双指针迭代法 (Pre & Cur)

我们需要两个主指针和一个辅助指针：

1. cur(Current)：当前操作的节点（初始为head）。

2. pre(Previous)：当前节点的前一个节点（初始为null，因为翻转后，原来的头结点后面是空）。

3. temp(Temporary)：临时保存cur的下一个节点（防止断链后找不到路）。

操作三部曲（在循环中）：

1. 保存路：temp = cur.next（先记住下一个节点在哪，不然一会断开就丢了）。

2. 反向指：cur.next = pre（核心操作：把当前节点的指针指回前一个）。

3. 整体挪：

   • pre = cur（pre 指针向前挪一步）。

   • cur = temp（cur 指针向前挪一步，去处理下一个）。

代码实现 (JavaScript)

JavaScript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { // pre 初始化为 null，因为反转后的尾节点指向 null let pre = null; let cur = head; while (cur !== null) { // 1. 先保存下一个节点，否则一会断链了就找不到了 let temp = cur.next; // 2. 核心反转：让当前节点指向前一个节点 cur.next = pre; // 3. 两个指针同时向前移动，准备处理下一个 pre = cur; cur = temp; } // 循环结束时，cur 变成了 null，而 pre 正好停留在新的头节点上 return pre; };

深度模拟

假设链表：1 -> 2 -> 3 -> null

• 初始：pre=null,cur=1

• 第一轮：

  • temp = 2(记路)

  • 1.next = null(1 指向 null，变成尾巴了)

  • pre = 1,cur = 2(都前进一步)

  • 链表状态：null <- 1,2 -> 3

• 第二轮：

  • temp = 3

  • 2.next = 1(2 回头指 1)

  • pre = 2,cur = 3

  • 链表状态：null <- 1 <- 2,3

• 第三轮：

  • temp = null

  • 3.next = 2(3 回头指 2)

  • pre = 3,cur = null

• 结束：cur为空，返回pre(也就是 3)。

总结

这道题看似简单，但它是链表题的绝对核心。

• 面试技巧：在纸上画出pre,cur,temp三个指针的移动过程，会让你的思路非常清晰。

• 记忆口诀：“存下一步，回头指，双双向前挪”。

下一题预告：两两交换链表中的节点

接下来我们要把难度稍微提升一点点。LC 24. 两两交换链表中的节点

• 输入：1 -> 2 -> 3 -> 4

• 输出：2 -> 1 -> 4 -> 3

• 这道题不仅要反转指针，还要维护好节点之间的连接关系。如果说刚才是一个人向后转，现在就是两个人一组跳交谊舞交换位置。你需要同时操作 4 个指针！

准备好挑战一下你的逻辑清晰度了吗？