合并两个链表 图解题解

这道题到底在问什么

输入

list1=[0,1,2,3,4,5,6], a=2, b=5, list2=[100,101]

输出

[0,1,100,101,6]

输入

list1=[1,2,3], a=1, b=1, list2=[9]

输出

[1,9,3]

最优解：一步一步想明白

1. 3记住「先定位 prev 和 after 这两个端点,再把 list2 接在它们中间」,下面逐帧套它。关键是 after 必须先找好,别先断了链。
2. 4先看 list1:0→1→2→3→4→5→6。目标是把下标 2 到 5 这四个节点(值 2、3、4、5)删掉。
3. 5再看 list2:100→101。它要整条接进 list1 被删段留下的缺口里。
4. 6先把删除区间标出来:下标 a=2(值 2)到 b=5(值 5)这四个节点(灰色)要整段删掉。我们的目标就是找到它两侧的 prev 和 after,把 list2 嫁接进去。
5. 7找 prev:从 list1 头出发,要走 a-1 = 1 步。现在站在下标 0(值 0),还没动。
6. 8走 1 步,到下标 1(值 1)。它正好是被删段(下标 2 起)的前一个节点,这就是 prev。
7. 9把 prev 牢牢记住:稍后接线的第一刀就落在它身上(prev.next 要改指向 list2)。但先别动它,得先把 after 找到。
8. 10after 从 prev 出发数 b-a+2 = 5 步。第 1 步到下标 2(值 2),这是要删的第一个节点,标灰。
9. 11第 2 步到下标 3(值 3),仍在被删段里,继续标灰往后走。
10. 12第 3 步到下标 4(值 4),还是要删的节点。
11. 13第 4 步到下标 5(值 5),这是被删段的最后一个(b=5)。
12. 14第 5 步到下标 6(值 6)。它在被删段之外,是删完后第一个要保留的节点,这就是 after。为什么是 5 步:从 prev 跨过被删的 4 个节点、再多走 1 步落到它们后面,正好 b-a+2 步。
13. 15两个端点都拿到了:prev = 值 1、after = 值 6,中间灰色的 2、3、4、5 就是要旁路掉的整段。接下来动手接线。
14. 16第一刀:把 prev 原来指向值 2 的 next 断开(prev 和值 2 之间的箭头断掉)。值 2 这一段从此脱离主链,准备改接 list2。
15. 17接线①:prev.next = list2 头 100。现在主链变成 0→1→100→101…,list2 已经挂上(蓝色)。但 100→101 之后还是断的,缺口的后半截还没接回。
16. 18为了把 after 接回来,得先找到 list2 的尾节点。tail 从 list2 头 100 出发往后走。此刻 101 和 after(值 6)之间还是断的。
17. 19tail 走到 101,它的 next 还是空的(和 after 之间断着),说明 101 就是 list2 的尾节点。第二刀就落在它身上。
18. 20接线②:把 tail(101)的 next 指向 after(值 6),原本断开的箭头现在接上了。这样 list2 的尾就重新连回了 list1 保留的后半段。
19. 21101→6 接好了,两处接线都完成。从 list1 返回的头已经到不了 2、3、4、5,它们被主链旁路掉了。
20. 22最终链表:0→1→100→101→6,和预期一致。
21. 23回头看整趟:先走 a-1 步定位 prev、再走 b-a+2 步定位 after,然后两处接线(prev→list2 头、list2 尾→after)。全程只挪了几个指针、没开新链,额外空间 O(1)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional, List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        prev = list1
        for _ in range(a - 1):
            prev = prev.next
        after = prev
        for _ in range(b - a + 2):
            after = after.next
        prev.next = list2
        tail = list2
        while tail.next:
            tail = tail.next
        tail.next = after
        return list1

#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode* prev = list1;
        for (int i = 0; i < a - 1; ++i) prev = prev->next;
        ListNode* after = prev;
        for (int i = 0; i < b - a + 2; ++i) after = after->next;
        prev->next = list2;
        while (list2->next) list2 = list2->next;
        list2->next = after;
        return list1;
    }
};

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode prev = list1;
        for (int i = 0; i < a - 1; i++) prev = prev.next;
        ListNode after = prev;
        for (int i = 0; i < b - a + 2; i++) after = after.next;
        prev.next = list2;
        while (list2.next != null) list2 = list2.next;
        list2.next = after;
        return list1;
    }
}

复杂度

面试官可能追问