7. 链表

约 7349 字大约 25 分钟

LeetcodePythonC++

2025-10-31

7. 链表

7.1 相交链表

160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。自定义评测：评测系统的输入如下（你设计的程序不适用此输入）：intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0； listA - 第一个链表；listB - 第二个链表；skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数；skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数；评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,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
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示
思路：两个指针分别从AB的起点开始遍历，如果遇到null，则跳转至对方的起点，继续往后走，这样可以确保相交时走的路程一样。
Python
```
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    p, q = headA, headB
    while p is not q:
        p = p.next if p else headB
        q = q.next if q else headA
    return p
```
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) {
        ListNode *p = headA, *q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};
```
时间复杂度： $O(m+n)$ ，其中 m 是第一条链表的长度，n 是第二条链表的长度。除了交点，每个节点会被指针 p 访问至多一次，每个节点会被指针 q 访问至多一次。
空间复杂度： $O(1)$ 。

7.2 反转链表

206. 反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：经典三指针法，pre cur nxt。

Python

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    pre = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = pre  # 把 cur 插在 pre 链表的前面（头插法）
        pre = cur
        cur = nxt
    return 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;
    }
};

时间复杂度： $O(n)$ ，其中 n 为链表节点个数。

空间复杂度： $O(1)$ 。

7.3 回文链表

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示

思路：一题更比三题强，找到中间节点->翻转中间节点后的部分->两头一起往中间遍历判断是否是回文。

Python

class Solution:
# 876. 链表的中间结点
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# 206. 反转链表
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    pre, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    mid = self.middleNode(head)
    head2 = self.reverseList(mid)
    while head2:
        if head.val != head2.val:  # 不是回文链表
            return False
        head = head.next
        head2 = head2.next
    return True

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 {
    ListNode *middleNode(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    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;
    }

public:
    bool isPalindrome(ListNode* head) {
        ListNode *middle = middleNode(head);
        ListNode *head2 = reverseList(middle);      
        while (head2) {
            if (head2->val != head->val) return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

时间复杂度： $O(n)$ ，其中 n 是链表的长度（节点个数）。

空间复杂度： $O(1)$ 。

7.4 环形链表

141. 环形链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：类似找寻中间节点的思想，用两个快慢指针，如果慢指针能追上快指针，说明有环。

Python

class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
    slow = fast = head  # 乌龟和兔子同时从起点出发
    while fast and fast.next:
        slow = slow.next  # 乌龟走一步
        fast = fast.next.next  # 兔子走两步
        if fast is slow:  # 兔子追上乌龟（套圈），说明有环
            return True
    return False  # 访问到了链表末尾，无环

C++

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

时间复杂度： $O(n)$ ，其中 n 是链表的长度。

空间复杂度： $O(1)$ 。

给定一个链表的头节点 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
解释：链表中没有环。

提示

思路：用了一个很巧妙的数学证明，从快慢指针相遇点再走a步就是入环口，a是头走到入环口的距离。

Python

class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast is slow:  # 相遇
            while slow is not head:  # 再走 a 步
                slow = slow.next
                head = head.next
            return slow
    return None

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 *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                while (head != slow) {
                    head = head->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

时间复杂度： $O(n)$ ，其中 n 是链表的长度。

空间复杂度： $O(1)$ 。

7.6 合并两个有序链表

21. 合并两个有序链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：使用一个哨兵作为起始结点，list1和list2谁小就加入谁，最后判断是否有剩余链表直接加入尾端。

Python

class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
    while list1 and list2:
        if list1.val < list2.val:
            cur.next = list1  # 把 list1 加到新链表中
            list1 = list1.next
        else:  # 注：相等的情况加哪个节点都是可以的
            cur.next = list2  # 把 list2 加到新链表中
            list2 = list2.next
        cur = cur.next
    cur.next = list1 or list2  # 拼接剩余链表
    return dummy.next

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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode temp;
        ListNode *cur = &temp;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            }
            else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        return temp.next;
    }
};

时间复杂度： $O(n + m)$ ，其中 n 是 list1 的长度，m 是 list2 的长度。

空间复杂度： $O(1)$ 。

7.7 两数相加

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]

提示

思路：使用一个哨兵作为起始结点，list1和list2谁小就加入谁，最后判断是否有剩余链表直接加入尾端。

Python

class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    cur = dummy = ListNode()  # 哨兵节点
    carry = 0  # 进位
    while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代
        if l1:
            carry += l1.val  # 节点值和进位加在一起
            l1 = l1.next  # 下一个节点
        if l2:
            carry += l2.val  # 节点值和进位加在一起
            l2 = l2.next  # 下一个节点
        cur.next = ListNode(carry % 10)  # 每个节点保存一个数位
        carry //= 10  # 新的进位
        cur = cur.next  # 下一个节点
    return dummy.next  # 哨兵节点的下一个节点就是头节点

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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode temp;
        ListNode *cur = &temp;
        int carry = 0;
        while (l1 || l2 || carry) {
            if (l1) {
                carry += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                carry += l2->val;
                l2 = l2->next;
            }
            cur->next = new ListNode(carry % 10);
            cur = cur->next;
            carry /= 10;
        }
        return temp.next;
    }
};

时间复杂度： $O(n)$ ，其中 n 为 $l_1$ 长度和 $l_2$ 长度的最大值。

空间复杂度： $O(1)$ 。

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

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]

提示

思路：使用一个哨兵作为起始结点，用两个指针组成一把尺子，当尺子右端移到尾端，说明尺子左端就是倒数第 n 个结点的位置。

Python

class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    # 由于可能会删除链表头部，用哨兵节点简化代码
    left = right = dummy = ListNode(next=head)
    for _ in range(n):
        right = right.next  # 右指针先向右走 n 步
    while right.next:
        left = left.next
        right = right.next  # 左右指针一起走
    left.next = left.next.next  # 左指针的下一个节点就是倒数第 n 个节点
    return dummy.next

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 temp(0, head);
        ListNode *left = &temp, *right = &temp;
        while (n--) {
            right = right->next;
        }
        while (right->next) {
            left = left->next;
            right = right->next;
        }
        ListNode *nxt = left->next;
        left->next = left->next->next;
        delete nxt;
        return temp.next;
    }
};

时间复杂度： $O(m)$ ，其中 m 为链表的长度。

空间复杂度： $O(1)$ 。

7.9 两两交换链表中的节点

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示

思路：使用一个哨兵作为起始结点，两个结点为一组依次翻转即可。

Python

class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    node0 = dummy = ListNode(next=head)  # 用哨兵节点简化代码逻辑
    node1 = head
    while node1 and node1.next:  # 至少有两个节点
        node2 = node1.next
        node3 = node2.next

        node0.next = node2  # 0 -> 2
        node2.next = node1  # 2 -> 1
        node1.next = node3  # 1 -> 3

        node0 = node1  # 下一轮交换，0 是 1
        node1 = node3  # 下一轮交换，1 是 3
    return dummy.next  # 返回新链表的头节点

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* swapPairs(ListNode* head) {
        ListNode temp(0, head);
        ListNode *pre = &temp;
        while (pre->next && pre->next->next) {
            ListNode *cur = pre->next, *nxt = pre->next->next;
            cur->next = nxt->next;
            nxt->next = cur;
            pre->next = nxt;
            pre = cur;
        }
        return temp.next;
    }
};

时间复杂度： $O(n)$ ，其中 n 为链表的长度。

空间复杂度： $O(1)$ 。

7.10 K 个一组翻转链表

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]

提示

思路：使用一个哨兵作为起始结点，先算出链表的长度，然后k个一组翻转。

Python

class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # 统计节点个数
    n = 0
    cur = head
    while cur:
        n += 1
        cur = cur.next

    p0 = dummy = ListNode(next=head)
    pre = None
    cur = head

    # k 个一组处理
    while n >= k:
        n -= k
        for _ in range(k):  # 同 92 题
            nxt = cur.next
            cur.next = pre  # 每次循环只修改一个 next，方便大家理解
            pre = cur
            cur = nxt

        # 见视频
        nxt = p0.next
        nxt.next = cur
        p0.next = pre
        p0 = nxt
    return dummy.next

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(0, head);
        ListNode *p = &dummy;
        int n = 0;
        while (head) {
            n++;
            head = head->next;
        }
        while (n >= k) {
            ListNode *pre = nullptr;
            ListNode *cur = p->next;
            for (int i = 0; i < k; i++) {
                ListNode *nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }
            ListNode *nxt = p->next;
            p->next = pre;
            nxt->next = cur;
            p = nxt;
            n -= k;
        }
        return dummy.next;
    }
};

时间复杂度： $O(n)$ ，其中 n 为链表的长度。

空间复杂度： $O(1)$ 。

7.11 随机链表的复制

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

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

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示

思路：先在原链表的每个结点的后面复制出一份拷贝结点，随机指针指向空；然后遍历这个新的链表，拷贝结点的随机指针就应该指向原结点的随机指针的next结点；最后分离这两个链表。

Python

class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if head is None:
        return None

    # 复制每个节点，把新节点直接插到原节点的后面
    cur = head
    while cur:
        cur.next = Node(cur.val, cur.next)
        cur = cur.next.next

    # 遍历交错链表中的原链表节点
    cur = head
    while cur:
        if cur.random:
            # 要复制的 random 是 cur.random 的下一个节点
            cur.next.random = cur.random.next
        cur = cur.next.next

    # 遍历交错链表中的新链表节点
    cur = head.next
    while cur.next:
        # 删除原链表的节点，即当前节点的下一个节点
        # 如果要恢复原链表，见另一份代码【Python3 写法二】
        cur.next = cur.next.next
        cur = cur.next

    # 返回 head.next 就相当于删除了原链表的头节点
    return head.next

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 == nullptr) {
            return nullptr;
        }
        for (Node *cur = head; cur; cur = cur->next->next) {
            cur->next = new Node(cur->val, cur->next, nullptr);
        }
        for (Node *cur = head; cur; cur = cur->next->next) {
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
        }
        Node *new_head = head->next;
        Node *cur = head;
        for (; cur->next->next; cur = cur->next) {
            Node *copy = cur->next;
            cur->next = copy->next;
            copy->next = copy->next->next;
        }
        cur->next = nullptr;
        return new_head;
    }
};

时间复杂度： $O(n)$ ，其中 n 为链表的长度。

空间复杂度： $O(1)$ 。

7.12 排序链表

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 = []
输出：[]

提示

思路：归并排序的思路。先将链表归到一项（链表的中间节点），然后并（合并两个链表）。

Python

class Solution:
# 876. 链表的中间结点（快慢指针）
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        pre = slow  # 记录 slow 的前一个节点
        slow = slow.next
        fast = fast.next.next
    pre.next = None  # 断开 slow 的前一个节点和 slow 的连接
    return slow

# 21. 合并两个有序链表（双指针）
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
    while list1 and list2:
        if list1.val < list2.val:
            cur.next = list1  # 把 list1 加到新链表中
            list1 = list1.next
        else:  # 注：相等的情况加哪个节点都是可以的
            cur.next = list2  # 把 list2 加到新链表中
            list2 = list2.next
        cur = cur.next
    cur.next = list1 if list1 else list2  # 拼接剩余链表
    return dummy.next

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 如果链表为空或者只有一个节点，无需排序
    if head is None or head.next is None:
        return head
    # 找到中间节点 head2，并断开 head2 与其前一个节点的连接
    # 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
    head2 = self.middleNode(head)
    # 分治
    head = self.sortList(head)
    head2 = self.sortList(head2)
    # 合并
    return self.mergeTwoLists(head, head2)

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 {
    ListNode *middleNode(ListNode* head) {
        ListNode *fast = head, *slow = head, *pre = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = nullptr;
        return slow;
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode*l2) {
        ListNode dummy;
        ListNode *p = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return dummy.next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *mid = middleNode(head);
        ListNode *l1 = sortList(head);
        ListNode *l2 =sortList(mid);
        ListNode *res = mergeTwoLists(l1, l2);
        return res;
    }
};

时间复杂度： $O(nlogn)$ ，其中 n 是链表长度。递归式 $T(n)=2T(n/2)+O(n)$ ，由主定理可得时间复杂度为 $O(nlogn)$ 。从图形上理解，递归深度是 $O(logn)$ ，每一层的链表长度之和是 $O(n)$ 。计算高为 $O(logn)$ ，底边长为 $O(n)$ 的矩形面积，得到 $O(nlogn)$ 。

空间复杂度： $O(logn)$ 。递归需要 $O(logn)$ 的栈开销。

7.13 合并 K 个升序链表

23. 合并 K 个升序链表

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

示例 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 = [[]]
输出：[]

提示

思路：也是归并的思路。先将链表均分成两份，然后并（合并两个链表）。

Python

class Solution:
# 21. 合并两个有序链表
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
    while list1 and list2:
        if list1.val < list2.val:
            cur.next = list1  # 把 list1 加到新链表中
            list1 = list1.next
        else:  # 注：相等的情况加哪个节点都是可以的
            cur.next = list2  # 把 list2 加到新链表中
            list2 = list2.next
        cur = cur.next
    cur.next = list1 if list1 else list2  # 拼接剩余链表
    return dummy.next

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    m = len(lists)
    if m == 0:
        return None
    if m == 1:
        return lists[0]  # 无需合并，直接返回
    left = self.mergeKLists(lists[:m // 2])  # 合并左半部分
    right = self.mergeKLists(lists[m // 2:])  # 合并右半部分
    return self.mergeTwoLists(left, right)  # 最后把左半和右半合并

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 {
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy;
        ListNode *p = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return dummy.next;
    }
    ListNode *mergeKLists(vector<ListNode*>& lists, int i, int j) {
        int n = j - i;
        if (n == 0) {
            return nullptr;
        }
        if (n == 1) {
            return lists[i];
        }
        ListNode *l1 = mergeKLists(lists, i, i + n / 2);
        ListNode *l2 = mergeKLists(lists, i + n / 2, j);
        return mergeTwoLists(l1, l2);
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeKLists(lists, 0, lists.size());
    }
};

时间复杂度： $O(Llogm)$ ，其中 m 为 lists 的长度，L 为所有链表的长度之和。每个节点参与链表合并的次数为 $O(logm)$ 次，一共有 L 个节点，所以总的时间复杂度为 $O(Llogm)$ 。

空间复杂度： $O(logm)$ 。递归深度为 $O(logm)$ ，需要 $O(logm)$ 的栈空间。Python 忽略切片产生的额外空间。

7.14 LRU 缓存

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例 1：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示

思路：用一个哈希表来存储key是否有对应的value，这样get()操作才能在O(1)时间完成。get：通过哈希判断key在不在，如果不在，直接返回-1；如果在，通过哈希拿到指向key缓存节点的指针，用splice剪切到链表头，然后返回value。put：通过哈希判断key在不在，如果在，通过哈希拿到指向key缓存节点的指针，用splice剪切到链表头，然后更新value；如果不在，通过emplace_front在头部插入，哈希表也要插入，再判断哈希表是否超额，超额则pop_back缓存表尾部，以及erase对应哈希记录。

Python

class LRUCache:
def __init__(self, capacity: int):
    self.capacity = capacity
    # from collections import OrderedDict
    # OrderedDict = dict + 双向链表
    self.cache = OrderedDict()  # key -> value

def get(self, key: int) -> int:
    if key not in self.cache:  # 没有这本书
        return -1
    # 有这本书，把这本书抽出来，放到最上面（last=False 表示移到链表头）
    self.cache.move_to_end(key, last=False)
    return self.cache[key]

def put(self, key: int, value: int) -> None:
    self.cache[key] = value  # 添加 key value 或者更新 value
    # 把这本书抽出来，放到最上面（last=False 表示移到链表头）
    self.cache.move_to_end(key, last=False)
    if len(self.cache) > self.capacity:  # 书太多了
        self.cache.popitem()  # 去掉最后一本书

C++

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache_list;
    unordered_map<int, list<pair<int, int>>::iterator> key_to_iter;
public:
    LRUCache(int capacity) : capacity(capacity){
    }
    
    int get(int key) {
        auto umap_iter = key_to_iter.find(key);
        if (umap_iter == key_to_iter.end()) {
            return -1;
        }
        auto list_iter = umap_iter->second;
        cache_list.splice(cache_list.begin(), cache_list, list_iter);
        return list_iter->second;
    }
    
    void put(int key, int value) {
        auto umap_iter = key_to_iter.find(key);
        if (umap_iter != key_to_iter.end()) {
            auto list_iter = umap_iter->second;
            list_iter->second = value;
            cache_list.splice(cache_list.begin(), cache_list, list_iter);
            return;
        }
        cache_list.emplace_front(key, value);
        key_to_iter[key] = cache_list.begin();
        if (key_to_iter.size() > capacity) {
            key_to_iter.erase(cache_list.back().first);
            cache_list.pop_back();
        }
    }
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

时间复杂度：所有操作均为 $O(1)$ 。

空间复杂度： $O(min(p,capacity))$ ，其中 p 为 put 的调用次数。