链表专题 | 算法笔记

203.移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/

简单

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

示例 2：

**输入：**head = [], val = 1 输出：[]

示例 3：

**输入：**head = [7,7,7,7], val = 7 输出：[]

提示：

列表中的节点数目在范围 [0, 10(4)] 内
1 <= Node.val <= 50
0 <= val <= 50

c++

/**
 * Definition for singly-linked list.
 * 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* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode;
        dummyHead->next = head;
        ListNode* cur = head;
        ListNode* pre = dummyHead;
        while (cur) {
            if (cur->val == val) {
                ListNode* tmp = cur;
                pre->next = cur->next;
                cur = cur->next;
                delete tmp;
            } else {
                pre = cur;
                cur = cur->next;
            }
        }
        return dummyHead->next;
    }
};

极简模板

cpp

dummy = new ListNode(0,head); cur=dummy;

while(cur->next){

if(cur->next->val==val){

temp=cur->next; cur->next=temp->next; delete temp;

}else cur=cur->next;

}

head=dummy->next; delete dummy; return head;

边界测试用例

1. 空链表：head=nullptr，任意val → 返回nullptr

2. 头节点为目标值：head=[1,2,3]，val=1 → [2,3]

3. 尾节点为目标值：head=[1,2,3]，val=3 → [1,2]

4. 全节点是目标值：head=[2,2,2]，val=2 → nullptr

5. 中间节点为目标值：head=[1,2,3,2]，val=2 → [1,3]

6. 单节点是目标值：head=[5]，val=5 → nullptr

7. 单节点非目标值：head=[5]，val=3 → [5]

8. 间隔目标值：head=[1,6,2,6,3]，val=6 → [1,2,3]

1. 虚拟头节点：规避头节点删除的特殊处理

2. 内存释放：C++手动delete，避免内存泄漏

3. 遍历逻辑：判断cur->next，防止空指针访问

707.设计链表

https://leetcode.cn/problems/design-linked-list/

中等

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3]

解释 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3 myLinkedList.get(1); // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

【初始化】

1. 建虚拟头节点dummy，指向null

2. 定义size=0，记录节点数

【get(index) 取值】

1. 先判越界：index<0/≥size → 直接返-1

2. cur指向dummy.next（真实头）

3. index次循环，cur=cur.next

4. 返cur.val

【addAtHead(val) 头插】

1. 新建节点newNode，值为val

2. newNode.next = dummy.next

3. dummy.next = newNode

4. size++

【addAtTail(val) 尾插】

1. cur指向dummy

2. 循环：cur.next不为空 → cur=cur.next

3. cur.next = 新建节点（值val）

4. size++

【addAtIndex(index,val) 插入】

1. 判index>size → 直接返回不操作

2. 若index<0 → 强制置index=0

3. cur指向dummy

4. index次循环，cur=cur.next

5. 新建newNode，值为val

6. newNode.next = cur.next

7. cur.next = newNode

8. size++

【deleteAtIndex(index) 删除】

1. 先判越界：index<0/≥size → 直接返回

2. cur指向dummy

3. index次循环，cur=cur.next

4. temp暂存cur.next（待删节点）

5. cur.next = temp.next

6. delete temp释放内存

7. size--

【通用必记3条】

1. 所有操作先判index越界，再执行

2. 增/删操作后，必须更新size

3. C++删除节点要手动delete，防泄漏

c++

class MyListNode {
public:
    MyListNode() : val(0), next(nullptr) {}
    MyListNode(int x) : val(x), next(nullptr) {}
    MyListNode(int x, MyListNode* nextNode) : val(x), next(nextNode) {}
    int val;
    MyListNode* next;
};

class MyLinkedList {
public:
    MyLinkedList() :size_(0), dummyHead_(new MyListNode) {
    }

    ~MyLinkedList() {
        delete dummyHead_;
    }

    int get(int index) {
        if (!(index >= 0 && index < size_)) {
            return -1;
        }
        MyListNode* pre = dummyHead_;
        for (int i = 0; i < index; ++i) {
            pre = pre->next;
        }
        return pre->next->val;
    }

    void addAtHead(int val) {
        MyListNode* node = new MyListNode(val);
        node->next = dummyHead_->next;
        dummyHead_->next = node;
        ++size_;
    }

    void addAtTail(int val) {
        MyListNode* node = new MyListNode(val);
        MyListNode* pre = dummyHead_;
        while (pre->next) {
            pre = pre->next;
        }
        pre->next = node;
        ++size_;
    }

    void addAtIndex(int index, int val) {
        if (index > size_) {
            return;
        }
        MyListNode* node = new MyListNode(val);
        MyListNode* pre = dummyHead_;
        for (int i = 0; i < index; ++i) {
            pre = pre->next;
        }
        node->next = pre->next;
        pre->next = node;
        ++size_;
    }

    void deleteAtIndex(int index) {
        if (!(index >= 0 && index < size_)) {
            return;
        }
        MyListNode* pre = dummyHead_;
        for (int i = 0; i < index; ++i) {
            pre = pre->next;
        }
        MyListNode* tmp = pre->next;
        pre->next = tmp->next;
        delete tmp;
        --size_;
    }

private:
    MyListNode* dummyHead_;
    int size_;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206. 反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

迭代

1. pre = nullptr （前面一开始是空）

2. cur = head （cur 从头开始走）

3. tmp = cur->next 先保住下一个节点

4. cur->next = pre 反转指向

5. pre = cur 、 cur = tmp 一起往前走

6. 最后 pre 就是新头

c++

/**
 * Definition for singly-linked list.
 * 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* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

递归

c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 没有节点或者只有一个节点
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 递归至最后一个节点
        // 移动head至最后一个节点
        ListNode* new_head = reverseList(head->next);
        // 递归逻辑
        // 让右侧节点指向自己
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    }
};

25. K 个一组翻转链表

给你链表的头节点 head ，每 k* *个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k* *的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

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

示例 2：

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

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

题解

一组反转结束后：
- pre指向这一组的头节点
- cur指向下一组的头节点。
- 上一组的尾节点指向这一组的尾节点

c++

/**
 * Definition for singly-linked list.
 * 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* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* p0 = dummy;

        // 计算链表节点个数
        int n = 0;
        for (ListNode* p = head; p != nullptr; p = p->next) {
            ++n;
        }

        for (; n >= k; n -= k) {
            for (int i = 0; i < k; ++i) {
                ListNode* tmp = cur->next;
                // "链式"
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }

            ListNode* tmp = p0->next;
            p0->next->next = cur;
            p0->next = pre;
            p0 = tmp;
        }

        return dummy->next;
    }
};

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

1. 建dummy，p=dummy（每组前驱锚点）

2. 循环条件：p->next和p->next->next都不为空（保证有两个节点可换）

3. 标记a=p->next（组第一个节点）、b=a->next（组第二个节点）

4. 三步交换：p->next=b → a->next=b->next → b->next=a

5. p后移到a（当前组尾，下一组前驱）

6. 释放dummy，return dummy->next

python

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode*dummy = new ListNode(0, head);
        ListNode*p = dummy;
        // 保证有两个节点可交换
        while(p->next && p->next->next){
            ListNode*a = p->next;
            ListNode*b = a->next;
            // 三步交换，无冗余
            p->next = b;
            a->next = b->next;
            b->next = a;
            // 指针后移，处理下一组
            p = a;
        }
        ListNode*res = dummy->next;
        delete dummy;
        return res;
    }
};

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n* *个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

**输入：**head = [1], n = 1 输出：[]

示例 3：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

c++

/**
 * Definition for singly-linked list.
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }

        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;

        return dummy->next;
    }
};

160. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

**输入：**intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 **输出：**Intersected at '8' **解释：**相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

**输入：**intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 **输出：**Intersected at '2' **解释：**相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

**输入：**intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 **输出：**null **解释：**从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 10(4)
1 <= Node.val <= 10(5)
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

**进阶：**你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

【双指针核心步骤】

1. 定义 pA=headA 、 pB=headB ，两个指针同时出发

2. 循环条件： pA != pB （相遇则终止）

3. 指针后移规则：走到尾就跳另一链表头，否则正常走

pA为空 → pA=headB，否则pA=pA->next
pB为空 → pB=headA，否则pB=pB->next

4. 循环结束，直接返回pA（或pB，相遇点/空指针二选一）

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) {
            return nullptr;
        }
        ListNode* pa = headA;
        ListNode* pb = headB;
        // 原理：走过相同的路程
        // pa和pb同为nullptr
        // pa和pb指向相交节点
        while (pa != pb) {
            pa = pa ? pa->next : headB;
            pb = pb ? pb->next : headA;
        }
        return pa;
    }
};

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

**不允许修改 **链表。

示例 1：

**输入：**head = [3,2,0,-4], pos = 1 **输出：**返回索引为 1 的链表节点 **解释：**链表中有一个环，其尾部连接到第二个节点。

示例 2：

**输入：**head = [1,2], pos = 0 **输出：**返回索引为 0 的链表节点 **解释：**链表中有一个环，其尾部连接到第一个节点。

示例 3：

**输入：**head = [1], pos = -1 **输出：**返回 null **解释：**链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10(4)] 内
-10(5) <= Node.val <= 10(5)
pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

题解

设链表中环外部分的长度为 a

slow 指针进入环后，又走了 b 的距离与 fast 相遇，slow走过的总距离为： a+b

fast 指针已经走完了环的 n 圈，因此fast走过的总距离为： a+n(b+c)+b=a+(n+1)b+nc。

fast 指针走过的距离为slow 指针的 2 倍：a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

时间复杂度：O(n)，其中 n 为链表的长度。
空间复杂度：O(1)，仅用到若干额外变量。

【快慢指针两步法】

1. 判环：slow=head、fast=head，slow走1步、fast走2步，循环至fast/faxt->next为空

2. 相遇则有环，未相遇则无环，直接返回null

3. 找入口：相遇后，p从表头出发，slow从相遇点出发，两者都走1步

4. p和slow相遇的节点，就是环的入口节点，直接返回

设：表头到入口距离为 a ，入口到相遇点距离为 b ，环剩余长度为 c ，环总长 b+c

慢指针走的距离： a+b
快指针走的距离： a+b+(b+c)*n （n为快指针绕环圈数，n≥1）
快指针速度是慢指针2倍 → 2(a+b) = a+b+(b+c)*n → 化简得 a = c + (n-1)*(b+c)
结论：表头到入口的距离a = 相遇点绕环到入口的距离c + 环的整数倍 → 因此p和slow同速走必在入口相遇

关键要点（避坑+加分）

1. 初始值：slow和fast都从head出发，而非虚拟头（本题无虚拟头）

2. 循环条件：必须判断 fast != nullptr && fast->next != nullptr ，防止空指针（快指针走2步）

3. 速度比：严格1步/2步，不可改，否则推导公式不成立

4. 找入口速度：p和slow必须同速走1步，而非快慢走

6. 无环判断：循环终止条件直接覆盖所有无环情况，无需额外判断

❌ 错误：fast初始值为head->next → 导致快慢指针步数差混乱，无法正确相遇
❌ 错误：找入口时p/slow不同速 → 永远遇不到入口
❌ 错误：循环条件只判断fast≠null → 会触发fast->next->next的空指针异常
✅ 所有判断/走步严格按模板来，无冗余操作，不会出错

哈希表法（易理解，适合兜底）：

1. 遍历链表，将所有节点地址存入 unordered_set

2. 若当前节点已在集合中，该节点即为环入口

3. 遍历结束无重复，说明无环，返回null

问：如何判断链表是否有环（141题）？答：用本题第一步判环，相遇则有环，无需找入口
问：快指针走3步可以吗？答：不可以，速度比非2倍会导致数学推导不成立，可能永远不相遇
问：找到入口后如何求环的长度？答：从入口出发，绕环走1圈回到入口，步数即为环长

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* node = head;
                while (node != slow) {
                    slow = slow->next;
                    node = node->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

**输入：**l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

**输入：**l1 = [], l2 = [] 输出：[]

示例 3：

**输入：**l1 = [], l2 = [0] 输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解

时间复杂度：O(n+m)，其中 n 为 list1 的长度，m 为 list2 的长度。
空间复杂度：O(1)。仅用到若干额外变量。

c++

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 创建一个虚拟头节点，方便处理
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    // 遍历两个链表，逐一比较节点值
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    // 将剩余的节点连接到结果链表上
    if (l1 != nullptr) {
        current->next = l1;
    } else {
        current->next = l2;
    }

    // 获取结果链表的头节点
    ListNode* head = dummy->next;
    delete dummy; // 释放虚拟头节点的内存
    return head;
}

// 打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    // 创建链表1: 1 -> 2 -> 4
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(2);
    list1->next->next = new ListNode(4);

    // 创建链表2: 1 -> 3 -> 4
    ListNode* list2 = new ListNode(1);
    list2->next = new ListNode(3);
    list2->next->next = new ListNode(4);

    // 合并链表
    ListNode* mergedList = mergeTwoLists(list1, list2);

    // 打印合并后的链表
    printList(mergedList);

    // 释放链表内存
    while (mergedList != nullptr) {
        ListNode* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}

递归版本

递归的核心是分治思想：把「合并两个长链表」拆解为「选当前小值节点 + 合并剩余的短链表」，直到触发终止条件（某链表为空），再逐层返回拼接结果，全程无需额外空间建节点，仅靠指针指向完成合并。

1. 终止条件：任一链表为空，直接返回另一链表（空链表和任何链表合并，结果都是另一个链表） 2. 递归递推：选当前值更小的节点，让它的 next 指向「自己的下一个节点 + 另一链表」的合并结果 3. 返回值：当前选中的小值节点（作为当前层合并后的链表头，供上层拼接）

python

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if(!l1)return l2;if(!l2)return l1;
    if(l1->val<l2->val){l1->next=mergeTwoLists(l1->next,l2);return l1;}
    else{l2->next=mergeTwoLists(l1,l2->next);return l2;}
}

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

**输入：**lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] **解释：**链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

示例 2：

**输入：**lists = [] 输出：[]

示例 3：

**输入：**lists = [[]] 输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

题解

使用一个优先队列（最小堆）来存储链表节点。
自定义比较器 cmp 确保优先队列按节点值排序。
将每个链表的头节点推入优先队列。
通过循环不断从优先队列中取出最小节点，将其加入结果链表，并将其后续节点（如果存在）推入优先队列。
返回合并后的链表头节点。

c++

/**
 * Definition for singly-linked list.
 * 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* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const ListNode* lhs, const ListNode* rhs) {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> que(cmp);
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i]) {
                que.push(lists[i]);
            }
        }
        ListNode dummy_head;
        ListNode* pre = &dummy_head;
        // 队列使用的直觉
        while (!que.empty()) {
            ListNode* node = que.top();
            que.pop();
            pre->next = node;
            pre = pre->next;
            if (node->next) {
                que.push(node->next);
            }
        }
        return dummy_head.next;
    }
};

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。**复制链表中的指针都不应指向原链表中的节点 **。

题解

第一遍遍历链表，创建新节点并使用哈希表存储原节点与新节点之间的映射关系。
第二遍遍历链表，利用哈希表中的映射关系更新每个新节点的 next 和 random 指

c++

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return NULL;
        }

        Node* cur = head;
        unordered_map<Node*, Node*> dic;
        while (cur) {
            dic[cur] = new Node(cur->val);
            cur = cur->next;
        }

        cur = head;
        Node* new_head = dic[cur];
        while (cur) {
            dic[cur]->next = dic[cur->next];
            dic[cur]->random = dic[cur->random];
            cur = cur->next;
        }

        return new_head;
    }
};

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围[1, 10(5)] 内
0 <= Node.val <= 9

**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题解

c++

/**
 * Definition for singly-linked list.
 * 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:
    bool isPalindrome(ListNode* head) {
        // 找到前半部分链表的尾节点
        ListNode* slow = head, *fast = head;
        while (fast) {
            slow = slow->next;
            if (fast->next) {
                fast = fast->next->next;
            } else {
                fast = fast->next;
            }
        }
        // 反转后半部分链表
        // 1 2 3 4 5
        //       s
        //           f
        // 1 2 3 4
        //     s
        //         f
        ListNode* r = reverseList(slow);
        ListNode* start = head;
        ListNode* tr = r;
        // 判断是否回文
        bool ret = true;
        while (r != nullptr) {
            if (r->val != start->val) {
                ret = false;
            }
            r = r->next;
            start = start->next;
        }
        // 恢复链表
        reverseList(tr);
        // 返回结果
        return ret;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

**输入：**l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] **解释：**342 + 465 = 807.

示例 2：

**输入：**l1 = [0], l2 = [0] 输出：[0]

示例 3：

**输入：**l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

题解

c++

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */

/*
同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加
p1: 跟踪l1
p2: 跟踪l2
head: 返回结果
tail: 尾插法建表
carry: 进位数
*/
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        ListNode* head = nullptr;
        ListNode* tail = nullptr;
        int carry = 0;
        int n1;
        int n2;
        while (p1 || p2) {
            n1 = p1 ? p1->val : 0;
            n2 = p2 ? p2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            if (p1) {
                p1 = p1->next;
            }
            if (p2) {
                p2 = p2->next;
            }
        }
        if (carry != 0) {
            tail->next = new ListNode(carry);
            tail = tail->next;
        }
        return head;
    }
};

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

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

示例 2：

**输入：**head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]

示例 3：

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

提示：

链表中节点的数目在范围 [0, 5 * 10(4)] 内
-10(5) <= Node.val <= 10(5)

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

203.移除链表元素 ​

极简模板 ​

边界测试用例 ​

707.设计链表 ​

203.移除链表元素

极简模板

边界测试用例

707.设计链表