← 返回首页 📚 实战课程
📑 本篇章节导航 (共5章,点击直达)
本节目标(学完能回答的面试题)核心知识(1小时精讲内容)面试速记卡(考前30秒速看)练习题(自测)学习资料

L12 - 算法入门-链表操作

本节目标(学完能回答的面试题)

核心知识(1小时精讲内容)

链表基础定义


// 单链表节点定义
public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

题目一:反转链表(LeetCode 206)

题目:给定单链表头节点,反转链表,返回新的头节点。

迭代法:


思路:逐个翻转每个节点的next指针

初始状态:
  1 → 2 → 3 → 4 → 5 → null
  ↑
 head

过程:
  prev = null, curr = head

  Step 1: curr=1
    next = curr.next = 2
    curr.next = prev = null     ← 翻转!
    prev = curr = 1
    curr = next = 2
    null ← 1    2 → 3 → 4 → 5 → null

  Step 2: curr=2
    next = curr.next = 3
    curr.next = prev = 1        ← 翻转!
    prev = curr = 2
    curr = next = 3
    null ← 1 ← 2    3 → 4 → 5 → null

  Step 3: curr=3
    null ← 1 ← 2 ← 3    4 → 5 → null

  Step 4: curr=4
    null ← 1 ← 2 ← 3 ← 4    5 → null

  Step 5: curr=5
    null ← 1 ← 2 ← 3 ← 4 ← 5
                                ↑ prev(新head)

  curr = null → 结束,返回 prev

// 迭代法
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next; // 保存后继
        curr.next = prev;          // 翻转指针
        prev = curr;               // prev前进
        curr = next;               // curr前进
    }
    return prev;
}
// 时间:O(n)  空间:O(1)

递归法:


递归思路:
  reverseList(head) 翻转以head开头的链表
  子问题:reverseList(head.next) 翻转后续链表

  1 → 2 → 3 → 4 → 5 → null

  递归到最深层:reverseList(5) → 返回5(新head)
  回溯:reverseList(4)
    head = 4, head.next = 5
    head.next.next = head → 5 → 4(翻转!)
    head.next = null → 5 → 4 → null
    返回 5

  reverseList(3):
    5 → 4 → 3 → null
  reverseList(2):
    5 → 4 → 3 → 2 → null
  reverseList(1):
    5 → 4 → 3 → 2 → 1 → null

// 递归法
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next); // 翻转后续
    head.next.next = head; // 后继节点指向自己
    head.next = null;      // 断开原来的next
    return newHead;
}
// 时间:O(n)  空间:O(n)(递归栈)

变体题:


题目二:环形链表(LeetCode 141 & 142)

141 - 判断是否有环:


快慢指针法(Floyd龟兔赛跑):
  slow 每次走1步
  fast 每次走2步

  如果无环:fast先到达null → 无环
  如果有环:fast在环内追上slow → 有环

图解:
  1 → 2 → 3 → 4 → 5 → 6
              ↑         │
              └─────────┘ (4→6→4,有环)

  slow: 1 → 2 → 3 → 4 → 5 → 6 → 4 ...
  fast: 1 → 3 → 5 → 4 → 6 → 4 ...  (fast在4追上slow)
  
  数学证明:
    设环长为C,slow进入环后,fast在环内某位置
    每一步 fast 比 slow 多走1步
    最多 C 步后 fast 追上 slow

// LeetCode 141
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;       // 走1步
        fast = fast.next.next;  // 走2步
        if (slow == fast) return true; // 相遇 → 有环
    }
    return false; // fast到达null → 无环
}
// 时间:O(n)  空间:O(1)

142 - 找环的入口节点:


阶段1:快慢指针找相遇点
阶段2:一个从head出发,一个从相遇点出发,速度都是1步
  → 再次相遇的节点就是环的入口!

数学推导:
  设 head 到环入口距离 = a
  环入口到相遇点距离 = b
  相遇点到环入口距离 = c
  环长 = b + c

  slow走了:a + b
  fast走了:a + b + k(b + c)(k圈)
  fast = 2 * slow:
    a + b + k(b + c) = 2(a + b)
    a + b + k(b + c) = 2a + 2b
    k(b + c) = a + b
    k(b + c) - b = a
    (k-1)(b+c) + c = a

  结论:a = c + (k-1)圈
  → 从head走a步 = 从相遇点走c步 + (k-1)圈 → 一定在环入口相遇!

// LeetCode 142
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // 阶段1:找相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 阶段2:找环入口
            ListNode p1 = head, p2 = slow;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1; // 环入口
        }
    }
    return null; // 无环
}
// 时间:O(n)  空间:O(1)

变体题:


题目三:合并两个有序链表(LeetCode 21)

题目:将两个升序链表合并为一个新的升序链表。


思路:双指针遍历,每次取较小的节点

  List1: 1 → 3 → 5 → null
  List2: 2 → 4 → 6 → null

  用哑节点(dummy)简化头节点处理:

  dummy → ?
  p1指向1, p2指向2

  Step 1: 1 < 2 → dummy.next = 1, p1前进
  dummy → 1 → ?
  p1指向3, p2指向2

  Step 2: 3 > 2 → tail.next = 2, p2前进
  dummy → 1 → 2 → ?
  p1指向3, p2指向4

  Step 3: 3 < 4 → tail.next = 3, p1前进
  dummy → 1 → 2 → 3 → ?
  p1指向5, p2指向4

  ...最终:dummy → 1 → 2 → 3 → 4 → 5 → 6
  返回 dummy.next

// 迭代法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1); // 哑节点
    ListNode tail = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    // 剩余部分直接接上
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}
// 时间:O(n+m)  空间:O(1)

// 递归法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}
// 时间:O(n+m)  空间:O(n+m)(递归栈)

变体题:


题目四:链表中间节点(LeetCode 876)

题目:找到链表的中间节点。如果有两个中间节点,返回第二个。


快慢指针法:
  slow走1步,fast走2步
  fast到末尾时,slow就在中间

  奇数长度:1 → 2 → 3 → 4 → 5
  slow: 1 → 2 → 3      → 返回3
  fast: 1 → 3 → 5 (null)

  偶数长度:1 → 2 → 3 → 4 → 5 → 6
  slow: 1 → 2 → 3      → 返回3(第二个中间节点)
  fast: 1 → 3 → 5 → null

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
// 时间:O(n)  空间:O(1)

如果要求返回第一个中间节点(偶数长度时):


// 返回第一个中间节点
public ListNode middleNodeFirst(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        // 注意条件不同:判断的是 fast.next 和 fast.next.next
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

题目五:删除链表倒数第N个节点(LeetCode 19)

题目:删除链表的倒数第n个节点,返回链表头节点。


思路:快慢指针,fast先走n步,然后slow和fast一起走

  示例:1 → 2 → 3 → 4 → 5,删除倒数第2个(4)

  Step 1: fast先走n=2步
  dummy → 1 → 2 → 3 → 4 → 5
  slow↑         fast↑

  Step 2: slow和fast一起走,直到fast到达末尾
  dummy → 1 → 2 → 3 → 4 → 5 → null
                  slow↑       fast↑

  Step 3: slow.next = slow.next.next(删除节点4)
  dummy → 1 → 2 → 3 → 4 → 5
                  slow↑  ↑ 跳过4
  结果:1 → 2 → 3 → 5

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head); // 哑节点处理删除头节点的情况
    ListNode slow = dummy, fast = dummy;

    // fast先走n步(注意:从dummy开始,走n步后fast指向第n个节点)
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }

    // slow和fast一起走,直到fast到达最后一个节点
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }

    // 删除slow的下一个节点
    slow.next = slow.next.next;
    return dummy.next;
}
// 时间:O(L) L=链表长度  空间:O(1)

变体题:


链表通用技巧总结


┌──────────────────────────────────────────────────────────────┐
│                   链表六大技巧                                │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  1. 哑节点(Dummy Node)                                     │
│     → 简化头节点的特殊处理(删除/插入头节点时)               │
│     → 几乎所有链表题都应该考虑是否需要                       │
│                                                              │
│  2. 快慢指针                                                 │
│     → 找中间节点:fast走2步,slow走1步                       │
│     → 检测环:fast走2步,slow走1步,相遇=有环                │
│     → 找倒数第N个:fast先走N步,再一起走                     │
│                                                              │
│  3. 双指针(前后指针)                                        │
│     → 合并有序链表:两个指针各遍历一条链表                    │
│     → 交集/差集:两条链表的公共节点                          │
│                                                              │
│  4. 翻转指针                                                 │
│     → 反转链表的核心:curr.next = prev                       │
│     → 记住三步:保存next → 翻转 → 前进                      │
│                                                              │
│  5. 递归                                                     │
│     → 反转链表、合并链表都有递归写法                         │
│     → 思考:子问题是什么?递归返回什么?当前层做什么?        │
│                                                              │
│  6. 画图!                                                   │
│     → 链表题最容易出错的是指针操作                           │
│     → 每一步画出节点和指针的指向                             │
│     → 特别注意:next指针的赋值顺序(先保存再修改)            │
│                                                              │
└──────────────────────────────────────────────────────────────┘

面试追问与回答

Q1: 反转链表的迭代法中,为什么要用next变量保存curr.next?

因为curr.next = prev会修改curr.next,如果不先保存,就无法移动到下一个节点。这是链表操作最常见的坑:修改指针前先保存。

Q2: 快慢指针为什么能检测环?数学上如何证明?

slow走1步,fast走2步,每步fast比slow多走1步。如果有环,fast在环内一定追上slow(因为每步距离缩小1)。如果无环,fast先到null。

Q3: 为什么删除倒数第N个节点需要哑节点?

如果删除的是头节点(倒数第L个,L为链表长度),没有哑节点时需要特殊处理head = head.next。有哑节点时,所有删除操作统一为slow.next = slow.next.next。

Q4: 合并K个有序链表(LeetCode 23)怎么做?

用最小堆(PriorityQueue)。将K个链表的头节点放入堆,每次弹出最小的节点加入结果,然后将该节点的next放入堆。时间O(N log K),N为总节点数,K为链表数。

Q5: 链表题最常见的bug是什么?

(1) 空指针异常:未检查null;(2) 指针修改顺序错误:先改了next导致后续节点丢失;(3) 死循环:链表成环(翻转时忘记断开原来的next);(4) 边界条件:单个节点、空链表、删除头节点。

面试速记卡(考前30秒速看)

练习题(自测)

1. 手动推演反转链表 [1,2,3,4,5] 的迭代过程,画出每一步三个指针的指向。

2. 编写环形链表II的代码,手动推演找环入口的过程(设定具体的环位置)。

3. 合并两个有序链表 [1,3,5] 和 [2,4,6],画出哑节点和两个指针的变化过程。

4. 删除链表 [1,2,3,4,5] 的倒数第2个节点,如果不使用哑节点,代码需要怎么处理边界?

5. 用递归法反转链表 [1,2,3],画出递归调用栈和每一步的链表状态变化。

学习资料