反转链表

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟢 简单
核心考察点：链表、递归、迭代

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

---

2. 解题思路拆解

方法：迭代法 (双指针/三指针)

这是最基础也最常用的链表操作。我们需要在遍历链表的过程中，将当前节点的 next 指针改为指向前一个节点。

由于节点没有引用前一个节点，因此必须事先存储前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

1. 初始化：

   • prev 指针指向 null（因为反转后的头节点，即原链表的尾节点，指向 null）。
   • curr 指针指向 head（当前处理的节点）。

2. 迭代过程：

   • 在改变 curr.next 之前，先记录 curr.next 为 next（防止断链）。
   • 将 curr.next 指向 prev（核心反转操作）。
   • prev 前移到 curr。
   • curr 前移到 next。

3. 结束条件：

   • 当 curr 为 null 时，循环结束。此时 prev 指向原链表的最后一个节点，也就是新链表的头节点。

---

3. 代码实现

/**
 * 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) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        const next = curr.next; // 1. 暂存后继节点
        curr.next = prev;       // 2. 修改引用指向前驱
        prev = curr;            // 3. prev 指针后移
        curr = next;            // 4. curr 指针后移
    }
    
    return prev;
};

代码执行演示

输入 1 -> 2 -> 3 -> null

• 初始：prev=null, curr=1
• 第 1 轮：
  • next = 2
  • 1.next 变 null (链表变成 null <- 1 2 -> 3)
  • prev = 1
  • curr = 2
• 第 2 轮：
  • next = 3
  • 2.next 变 1 (链表变成 null <- 1 <- 2 3)
  • prev = 2
  • curr = 3
• 第 3 轮：
  • next = null
  • 3.next 变 2 (链表变成 null <- 1 <- 2 <- 3)
  • prev = 3
  • curr = null
• 循环结束，返回 prev (也就是 3)。

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。需要遍历链表一次。
空间复杂度	$O(1)$。只使用了常数个指针变量。