7. 链表
约 7349 字大约 25 分钟
LeetcodePythonC++
2025-10-31
7. 链表
7.1 相交链表
- 给你两个单链表的头节点 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,则跳转至对方的起点,继续往后走,这样可以确保相交时走的路程一样。
Pythonclass 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 pC++/** * 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 反转链表
- 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]示例 2:输入:head = [1,2]
输出:[2,1]示例 3:输入:head = []
输出:[]提示
思路:经典三指针法,pre cur nxt。
Pythonclass 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 preC++/** * 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 回文链表
- 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。示例 1:
输入:head = [1,2,2,1]
输出:true示例 2:输入:head = [1,2]
输出:false提示
思路:一题更比三题强,找到中间节点->翻转中间节点后的部分->两头一起往中间遍历判断是否是回文。
Pythonclass 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 TrueC++/** * 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 环形链表
- 给你一个链表的头节点 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
解释:链表中没有环。提示
思路:类似找寻中间节点的思想,用两个快慢指针,如果慢指针能追上快指针,说明有环。
Pythonclass 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)。
7.5 环形链表 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
解释:链表中没有环。提示
思路:用了一个很巧妙的数学证明,从快慢指针相遇点再走a步就是入环口,a是头走到入环口的距离。
Pythonclass 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 NoneC++/** * 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 合并两个有序链表
- 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 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谁小就加入谁,最后判断是否有剩余链表直接加入尾端。
Pythonclass 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.nextC++/** * 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 两数相加
- 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 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谁小就加入谁,最后判断是否有剩余链表直接加入尾端。
Pythonclass 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 为 l1 长度和 l2 长度的最大值。
空间复杂度:O(1)。
7.8 删除链表的倒数第 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 个结点的位置。
Pythonclass 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.nextC++/** * 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 两两交换链表中的节点
- 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]示例 2:输入:head = []
输出:[]示例 3:输入:head = [1]
输出:[1]提示
思路:使用一个哨兵作为起始结点,两个结点为一组依次翻转即可。
Pythonclass 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 个一组翻转链表
- 给你链表的头节点 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个一组翻转。
Pythonclass 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.nextC++/** * 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 随机链表的复制
- 给你一个长度为 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结点;最后分离这两个链表。
Pythonclass 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.nextC++/* // 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 排序链表
- 给你链表的头结点 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 = []
输出:[]提示
思路:归并排序的思路。先将链表归到一项(链表的中间节点),然后并(合并两个链表)。
Pythonclass 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 个升序链表
- 给你链表的头结点 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 = [[]]
输出:[]提示
思路:也是归并的思路。先将链表均分成两份,然后并(合并两个链表)。
Pythonclass 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 缓存
- 请你设计并实现一个满足 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对应哈希记录。
Pythonclass 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 的调用次数。
