算法 - 反转链表 (Reverse Linked List)

Posted on

1. 题目

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

示例:

1
2
3
4
5
输入: 1 -> 2 -> 3 -> 4 -> 5
输出: 5 -> 4 -> 3 -> 2 -> 1

输入: head = []
输出: []

链表节点定义：

1
2
3
4
5
6
7
8
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

2. 解题思路

2.1 迭代（首选）

反转的本质是把每个节点的 next 指针掉头，指向它原来的前驱。用三个指针：

  • prev：已反转部分的头，初始 null。
  • curr：当前正在处理节点，初始 head。
  • nextTemp：在处理前先保存 curr.next，否则断链后找不到后继。

每一步：暂存后继 → curr.next = prev → prev 前移到 curr → curr 前移到暂存的后继。循环结束时 prev 就是新头。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

2.2 递归

递归到链表末尾，回溯时把后一个节点的 next 指回自己：head.next.next = head，再断开 head.next = null 防止成环。简洁但栈空间 O(n)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 迭代
function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;

    while (curr !== null) {
        const nextTemp = curr.next; // 1. 暂存后继
        curr.next = prev;           // 2. 反转指针
        prev = curr;                // 3. prev 前进
        curr = nextTemp;            // 4. curr 前进
    }

    return prev;
}

// 递归
function reverseListRecursive(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;

    const newHead = reverseListRecursive(head.next);
    head.next.next = head; // 让后继指回自己
    head.next = null;      // 断开原指针，避免环
    return newHead;
}

4. 面试延伸

  • 反转区间（LeetCode 92 反转链表 II） 或 每 k 个一组翻转（25 题） 是高频进阶，核心仍是本节的指针操作，外加「哑节点 dummy」简化边界。
  • 判断回文链表（234）：快慢指针找中点 + 反转后半段 + 逐一比较，空间 O(1)。
  • 递归版本要能徒手画图讲清 head.next.next = head 的含义，这是面试官最爱追问的点。

难度：简单 | LeetCode 206 题 | 链表题地基