跳到主要内容

反转链表

问题​

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

示例：

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

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

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

来源：LeetCode 206. 反转链表

前置知识​

ListNode.ts
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

答案​

方法一：迭代（推荐）​

核心思路：遍历链表，把每个节点的 next 指针反转指向前一个节点。需要三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点，用于暂存）。

reverseListIterative.ts
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next;  // 暂存下一个节点
    curr.next = prev;        // 反转指针
    prev = curr;             // prev 前进
    curr = next;             // curr 前进
  }

  return prev; // prev 变成了新的头节点
}

图解过程：

初始：prev = null, curr = 1

Step 1: next = 2, 1.next = null, prev = 1, curr = 2
  null ← 1    2 → 3 → 4 → 5
        prev  curr

Step 2: next = 3, 2.next = 1, prev = 2, curr = 3
  null ← 1 ← 2    3 → 4 → 5
              prev  curr

Step 3: next = 4, 3.next = 2, prev = 3, curr = 4
  null ← 1 ← 2 ← 3    4 → 5
                  prev  curr

Step 4: next = 5, 4.next = 3, prev = 4, curr = 5
  null ← 1 ← 2 ← 3 ← 4    5
                      prev  curr

Step 5: next = null, 5.next = 4, prev = 5, curr = null
  null ← 1 ← 2 ← 3 ← 4 ← 5
                          prev  curr(null)

返回 prev = 5，即新的头节点
复杂度分析
  • 时间复杂度：O(n)O(n) — 遍历一次链表
  • 空间复杂度：O(1)O(1) — 只用了几个指针变量

方法二：递归​

核心思路：先递归到链表末尾，回溯时逐层反转指针。

reverseListRecursive.ts
function reverseList(head: ListNode | null): ListNode | null {
  // 递归终止：空链表或到达最后一个节点
  if (head === null || head.next === null) {
    return head;
  }

  // 递归反转后面的链表，newHead 是反转后的头（即原链表的尾）
  const newHead = reverseList(head.next);

  // 回溯时反转指针
  head.next.next = head; // 让下一个节点指向自己
  head.next = null;      // 断开原来的正向连接

  return newHead;
}

递归展开：

reverseList(1→2→3→4→5)
  reverseList(2→3→4→5)
    reverseList(3→4→5)
      reverseList(4→5)
        reverseList(5)
          return 5  ← 到达终止条件

        // 回到 head=4 这层
        4.next.next = 4  → 5.next = 4 → 5→4
        4.next = null                  → 5→4→null
        return 5

      // 回到 head=3 这层
      3.next.next = 3  → 4.next = 3 → 5→4→3
      3.next = null                  → 5→4→3→null
      return 5

    // ... 依此类推
  return 5                           → 5→4→3→2→1→null
复杂度分析
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n) — 递归调用栈

递归虽然代码更简洁，但链表长度大时可能栈溢出。面试建议优先写迭代法。

方法三：头插法​

核心思路：摘下每个节点，插入到新链表的头部。

reverseListHeadInsert.ts
function reverseList(head: ListNode | null): ListNode | null {
  let newHead: ListNode | null = null;

  while (head !== null) {
    const next = head.next;  // 暂存
    head.next = newHead;     // 当前节点插入新链表头部
    newHead = head;          // 更新新链表头
    head = next;             // 继续处理下一个
  }

  return newHead;
}
与方法一本质相同

头插法和方法一的迭代法本质是一样的逻辑，只是变量命名和理解角度不同。方法一从"反转指针"角度理解，头插法从"构建新链表"角度理解。

方法四：利用数组（不推荐）​

先把值存入数组，反转数组后重建链表：

reverseListArray.ts
function reverseList(head: ListNode | null): ListNode | null {
  const values: number[] = [];
  let p = head;
  while (p) {
    values.push(p.val);
    p = p.next;
  }

  // 反向重建
  const dummy = new ListNode(-1);
  let current = dummy;
  for (let i = values.length - 1; i >= 0; i--) {
    current.next = new ListNode(values[i]);
    current = current.next;
  }

  return dummy.next;
}
不推荐
  • 空间复杂度：O(n)O(n) — 额外数组
  • 没有利用链表的特性，面试中使用只能说明"会做"但不够好

常见面试追问​

Q1: 如何反转链表的第 m 到 n 个节点？​

答案：LeetCode 92. 反转链表 II

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  const dummy = new ListNode(-1, head);
  let prev = dummy;

  // 走到 left 的前一个节点
  for (let i = 1; i < left; i++) {
    prev = prev.next!;
  }

  const curr = prev.next!;
  // 头插法反转 left 到 right 之间的节点
  for (let i = 0; i < right - left; i++) {
    const next = curr.next!;
    curr.next = next.next;
    next.next = prev.next;
    prev.next = next;
  }

  return dummy.next;
}

Q2: 如何 K 个一组反转链表？​

答案：LeetCode 25. K 个一组翻转链表，这是字节跳动面试的高频题：

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  // 检查剩余节点是否够 k 个
  let check = head;
  for (let i = 0; i < k; i++) {
    if (!check) return head; // 不够 k 个，不反转
    check = check.next;
  }

  // 反转前 k 个节点
  let prev: ListNode | null = null;
  let curr = head;
  for (let i = 0; i < k; i++) {
    const next = curr!.next;
    curr!.next = prev;
    prev = curr;
    curr = next;
  }

  // head 变成了这组的尾部，连接下一组的反转结果
  head!.next = reverseKGroup(curr, k);

  return prev; // prev 是这组反转后的头
}

Q3: 如何判断链表是否有环？​

答案：使用快慢指针（Floyd 判环算法），这是链表类题目的重要延伸：

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

相关链接​