LeetCode链表章节（持续更新中）

简单 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 <= 100l1 和 l2 均按 非递减顺序 排列

递归，问题可以化为重复子问题，既不断合并两个链表，所以可以采用递归

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if (list1 == nullptr) return list2; if (list2 == nullptr) return list1; if (list1->val < list2->val) { list1->next = mergeTwoLists(list1->next, list2); return list1; } else { list2->next = mergeTwoLists(list1, list2->next); return list2; } }

迭代

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* newhead = new ListNode; ListNode* cur = newhead; 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); ListNode* ans = newhead->next; delete newhead; return ans; } 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 解释：链表中没有环。

提示：

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

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

哈希

如果链表中存在环，链表中有重复的地址出现；如果没有环，则退出循环。 bool hasCycle(ListNode *head) { unordered_set<ListNode* > hash; while (head) { if (hash.count(head)) return true; hash.insert(head); head = head->next; } return false; }

快慢指针

如果链表中存在环，那么 fast 指针会先进入环，然后在环中不断循环。由于 fast 指针移动速度比 slow 指针快，最终 fast 指针会追上 slow 指针，即 slow 指针和 fast 指针会相遇。如果链表中不存在环，那么 fast 指针会先到达链表的末尾（即 fast->next 或 fast->next->next 为 nullptr），此时循环结束，说明链表中不存在环。 bool hasCycle(ListNode *head) { if (head == nullptr) return false; ListNode* slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } 160. 相交链表

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

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

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

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

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0listA - 第一个链表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 。

提示：

listA 中节点数目为 mlistB 中节点数目为 n1 <= m, n <= 3 * 10^41 <= Node.val <= 10^50 <= skipA <= m0 <= skipB <= n如果 listA 和 listB 没有交点，intersectVal 为 0如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

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

哈希

找到第一个重复出现的地址。 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode* > hash; while (headA) { hash.insert(headA); headA = headA->next; } while (headB) { if (hash.count(headB)) return headB; headB = headB->next; } return nullptr; }

双指针

指针 curA 先遍历链表 A 的不相交部分，长度为 a - c；然后遍历相交部分，当遍历到相交部分末尾时，如果还没有和 curB 相遇，它会跳到链表 B 的头部继续遍历。此时它总共遍历的节点数为 a - c + b - c。

指针 curB 先遍历链表 B 的不相交部分，长度为 b - c；然后遍历相交部分，当遍历到相交部分末尾时，如果还没有和 curA 相遇，它会跳到链表 A 的头部继续遍历。此时它总共遍历的节点数为 b - c + a - c。

如果没有相交节点，c = 0，curA和curB会在都为空时相遇，并退出循环。

图片原题解

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == nullptr || headB == nullptr) return nullptr; ListNode* curA = headA, * curB = headB; while (curA != curB) { curA = curA == nullptr ? headB : curA->next; curB = curB == nullptr ? headA : curB->next; } return curA; } 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

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

迭代

ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* prev = nullptr; while (cur) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

递归

ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* new_head = reverseList(head->next); head->next->next = head; head->next = nullptr; 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) 空间复杂度解决此题？

数组模拟

bool isPalindrome(ListNode* head) { vector<int> nums; while (head) { nums.push_back(head->val); head = head->next; } int left = 0, right = nums.size() - 1; while (left < right) { if (nums[left] != nums[right]) return false; left++; right--; } return true; }

找到链表的中间节点，再逆置后比对

// 876. 链表的中间结点 ListNode* middleNode(ListNode* head) { ListNode* slow = head, * fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } // 206. 反转链表 ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* prev = nullptr; while (cur) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } bool isPalindrome(ListNode* head) { ListNode* mid = middleNode(head); mid = reverseList(mid); while (mid) { if (head->val != mid->val) return false; head = head->next; mid = mid->next; } return true; } 876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

链表的结点数范围是 [1, 100]1 <= Node.val <= 100

快慢指针

ListNode* middleNode(ListNode* head) { ListNode* slow = head, * fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } 中等 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题目数据保证列表表示的数字不含前导零

根据题意，将链表中的两数相加即可；通过创建newhead，可以避免新链表判断是否有头节点。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int t = 0, sum = 0; ListNode* newhead = new ListNode; ListNode* cur = newhead; ListNode* cur1 = l1,* cur2 = l2; while (cur1 && cur2) { sum = cur1->val + cur2->val + t; cur->next = new ListNode(sum % 10); cur = cur->next; t = sum / 10; cur1 = cur1->next; cur2 = cur2->next; } while (cur1) { sum = cur1->val + t; cur->next = new ListNode(sum % 10); cur = cur->next; t = sum / 10; cur1 = cur1->next; } while (cur2) { sum = cur2->val + t; cur->next = new ListNode(sum % 10); cur = cur->next; t = sum / 10; cur2 = cur2->next; } if (t) cur->next = new ListNode(t); return newhead->next; }

对上面代码进行优化。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int sum = 0; ListNode* newhead = new ListNode; ListNode* cur = newhead; ListNode* cur1 = l1,* cur2 = l2; while (cur1 || cur2 || sum) { if (cur1) { sum += cur1->val; cur1 = cur1->next; } if (cur2) { sum += cur2->val; cur2 = cur2->next; } cur->next = new ListNode(sum % 10); cur = cur->next; sum /= 10; } return newhead->next; } 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]

提示：

链表中结点的数目为 sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz

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

计算链表长度，转化为删除链表第(len - n)个节点。

ListNode* removeNthFromEnd(ListNode* head, int n) { int len = 0; ListNode* cur = head; while (cur) { cur = cur->next; len++; } int k = len - n; cur = head; ListNode* prev = nullptr; while (k--) { prev = cur; cur = cur->next; } if (prev == nullptr) return head->next; prev->next = cur->next; return head; }

快慢指针，fast指针快slow指针(n + 1)个，当fast为空时，slow刚好为要删除的节点前一个

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* new_head = new ListNode(0, head); ListNode* fast = head; ListNode* slow = new_head; while (n--) { fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } slow->next = slow->next->next; ListNode* ans = new_head->next; delete new_head; return ans; } 24. 两两交换链表中的节点

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

递归

ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* newhead = head->next; // 先交换当前两个节点后面的节点，再交换当前两个节点 head->next = swapPairs(newhead->next); newhead->next = head; return newhead; }

迭代，将需要交换的左右节点，以及左节点的前节点和后节点定义，便于交换操作。

ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* newhead = new ListNode(0, head); ListNode* prev = newhead; ListNode* left = head; ListNode* right = head->next; ListNode* next = right->next; while (left && right) { left->next = next; right->next = left; prev->next = right; prev = left; left = prev->next; if (left) right = left->next; if (right) next = right->next; } return newhead->next; } 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]]

提示：

0 <= n <= 1000-10^4 <= Node.val <= 10^4Node.random 为 null 或指向链表中的节点。

递归回溯

// 旧节点对应新节点 unordered_map<Node*, Node*> cache_node; Node* copyRandomList(Node* head) { if (head == nullptr) return nullptr; if (!cache_node.count(head)) { // 未复制这个节点 Node* new_node = new Node(head->val); cache_node[head] = new_node; new_node->next = copyRandomList(head->next); new_node->random = copyRandomList(head->random); } return cache_node[head]; }

迭代 + 节点拆分，对于链表 A→B→C，我们可以将其拆分为 A→A ′ →B→B ′ →C→C ′ 。对于任意一个原节点 S，其拷贝节点 S ′即为其后继节点。

Node* copyRandomList(Node* head) { if (head == nullptr) return nullptr; // 插入新节点到原链表中 for (Node* cur = head; cur != nullptr; cur = cur->next->next) { Node* new_node = new Node(cur->val); new_node->next = cur->next; cur->next = new_node; } // 复制随机指针 for (Node* cur = head; cur != nullptr; cur = cur->next->next) { Node* new_node = cur->next; new_node->random = (cur->random ? cur->random->next : nullptr); } // 拆分链表 Node* new_head = head->next; for (Node* cur = head; cur != nullptr; cur = cur->next) { Node* new_node = cur->next; cur->next = cur->next->next; new_node->next = (new_node->next ? new_node->next->next : nullptr); } return new_head; } 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] 内-105 <= Node.val <= 10^5pos 的值为 -1 或者链表中的一个有效索引

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

哈希

如果链表中存在环，链表中第一次重复出现的地址就是入环的第一个节点；如果没有环，则退出循环。 ListNode *detectCycle(ListNode *head) { unordered_set<ListNode* > hash; while (head) { if (hash.count(head)) return head; hash.insert(head); head = head->next; } return nullptr; }

快慢指针

设链表头节点到环入口节点的距离为 a，环入口节点到快慢指针相遇节点的距离为 b，相遇节点再到环入口节点的距离为 c。

当快慢指针相遇时，slow 指针走过的距离为 a + b，fast 指针走过的距离为 a + b + k * (b + c)（k 为 fast 指针在环内绕的圈数，k >= 1）。由于 fast 指针速度是 slow 指针的两倍，所以有 2 * (a + b) = a + b + k * (b + c)，化简可得 a = (k - 1) * (b + c) + c，既a等于c加上k - 1圈的长度。这意味着从链表头节点和快慢指针相遇节点同时出发，以相同速度前进，它们会在环的入口节点相遇。 ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { while (head != slow) { head = head->next; slow = slow->next; } return slow; } } return nullptr; } 143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

示例 1：

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

示例 2：

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

提示：

链表的长度范围为 [1, 5 * 104]1 <= node.val <= 1000

876. 链表的中间结点 + 206. 反转链表 + 合并链表

ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } void reorderList(ListNode* head) { ListNode* mid = middleNode(head); ListNode* l1 = head; ListNode* l2 = mid->next; mid->next = nullptr; l2 = reverseList(l2); // 合并 while (l1 && l2) { ListNode* l1_tmp = l1->next; ListNode* l2_tmp = l2->next; l1->next = l2; l1 = l1_tmp; l2->next = l1; l2 = l2_tmp; } } 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) 的平均时间复杂度运行。

示例：

输入 ["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

提示：

1 <= capacity <= 30000 <= key <= 100000 <= value <= 105最多调用 2 * 105 次 get 和 put

哈希表 + 双向链表

get和put方法 要求O(1) 的平均时间复杂度，所以想到用哈希表；用带伪头节点和伪尾节点双向链表来维护缓存，便于不断更新头节点，删除节点；

get 方法

尝试从哈希表中查找键为 key 的节点。如果节点不存在，返回 -1。如果节点存在，将该节点移动到双向链表的头部（表示最近使用），然后返回节点的值。

put 方法

如果键key不存在于缓存中：

创建一个新的节点，并将其插入到双向链表的头部。将该节点的信息存入哈希表。如果缓存大小超过容量，删除双向链表的尾节点（即最近最少使用的节点），并从哈希表中移除对应的记录。

如果键key已经存在于缓存中：

更新该节点的值。将该节点移动到双向链表的头部 struct DLinkNode { int key, value; DLinkNode* next; DLinkNode* prev; DLinkNode() : key(0), value(0), next(nullptr), prev(nullptr) {} DLinkNode(int key_, int value_) : key(key_), value(value_), next(nullptr), prev(nullptr) {} }; class LRUCache { private: DLinkNode* head_; // 伪头部 DLinkNode* tail_; // 伪尾部 unordered_map<int, DLinkNode*> cache_; int size_; int capacity_; public: LRUCache(int capacity) : size_(0), capacity_(capacity) { head_ = new DLinkNode(); tail_ = new DLinkNode(); head_->next = tail_; tail_->prev = head_; } int get(int key) { if (!cache_.count(key)) return -1; DLinkNode* node = cache_[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (!cache_.count(key)) { // key不存在，创建新节点 DLinkNode* node = new DLinkNode(key, value); cache_[key] = node; addToHead(node); ++size_; if (size_ > capacity_) { // 超出缓存容量，删除尾节点 DLinkNode* removed = removeTail(); cache_.erase(removed->key); delete removed; --size_; } } else { // key存在，更新value，移至头部 DLinkNode* node = cache_[key]; node->value = value; moveToHead(node); } } private: void removeNode(DLinkNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void addToHead(DLinkNode* node) { DLinkNode* head = head_->next; head->prev = node; node->next = head; head_->next = node; node->prev = head_; } void moveToHead(DLinkNode* node) { removeNode(node); addToHead(node); } DLinkNode* removeTail() { DLinkNode* node = tail_->prev; removeNode(node); return node; } }; 147. 对链表进行插入排序

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

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

示例 2：

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

提示：

列表中的节点数在 [1, 5000]范围内-5000 <= Node.val <= 5000 ListNode* insertionSortList(ListNode* head) { ListNode* new_head = new ListNode(0, head); ListNode* cur = head->next; ListNode* prev = head; while (cur) { if (cur->val < prev->val) { ListNode* pos = new_head; while (pos->next->val <= cur->val) pos = pos->next; prev->next = cur->next; cur->next = pos->next; pos->next = cur; } prev = cur; cur = cur->next; } ListNode* ans = new_head->next; delete new_head; return ans; } 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 * 104] 内-105 <= Node.val <= 105

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

归并排序，通过快慢指针找到中间节点，递归地对链表进行分治排序。

ListNode* merge(ListNode* list1, ListNode* list2) { ListNode* new_head = new ListNode; ListNode* cur = new_head; 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); ListNode* head = new_head->next; delete new_head; return head; } ListNode* sortList(ListNode* head, ListNode* tail) { if (head == nullptr) return head; if (head->next == tail) { head->next = nullptr; return head; } ListNode* slow = head, * fast = head; while (fast != tail && fast->next != tail) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow; return merge(sortList(head, mid), sortList(mid, tail)); } ListNode* sortList(ListNode* head) { return sortList(head, nullptr); } 困难 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4

暴力解法

根据21. 合并两个有序链表这题，不断合并所有链表。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* newhead = new ListNode; ListNode* cur = newhead; 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 newhead->next; } ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* ans = nullptr; for (ListNode* list : lists) ans = mergeTwoLists(ans, list); return ans; }

分治合并

和归并排序的思想一样，不断将链表的头节点分成两部分，先分别对这两部分合并，再将这两部分合并。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* new_head = new ListNode; ListNode* cur = new_head; 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 new_head->next; } ListNode* merge(vector<ListNode*>& lists, int left, int right) { if (left > right) return nullptr; if (left == right) return lists[left]; int mid = left + (right - left) / 2; return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right)); } ListNode* mergeKLists(vector<ListNode*>& lists) { int n = lists.size(); return merge(lists, 0, n - 1); }

优先级队列

借助优先级队列找到最小的未被合并的头节点，不断合并。

struct cmp { bool operator()(ListNode* list1, ListNode* list2) { return list1->val > list2->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { // 建立小根堆 priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // 所有头节点入队 for (ListNode* list : lists) if (list) heap.push(list); // 合并k个有序链表 ListNode* new_head = new ListNode; ListNode* cur = new_head; while (!heap.empty()) { ListNode* t = heap.top(); heap.pop(); if (t->next) heap.push(t->next); cur->next = t; cur = cur->next; } return new_head->next; } 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]

提示：

链表中的节点数目为 n1 <= k <= n <= 50000 <= Node.val <= 1000

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

模拟

每k个节点进行一次206. 反转链表，并记录新的头和尾用于整个链表的连接。

pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) { ListNode* prev = tail->next; ListNode* cur = head; while (prev != tail) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return {tail, head}; } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* new_head = new ListNode(0, head); ListNode* cur = new_head; while (cur) { ListNode* tail = cur; for (int i = 0; i < k; ++i) { tail = tail->next; if (tail == nullptr) return new_head->next; } auto p = reverseList(cur->next, tail); head = p.first; tail = p.second; cur->next = head; cur = tail; } return new_head->next; }

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]

提示：

链表中的节点数目为 n1 <= k <= n <= 50000 <= Node.val <= 1000

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

模拟

每k个节点进行一次206. 反转链表，并记录新的头和尾用于整个链表的连接。

pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) { ListNode* prev = tail->next; ListNode* cur = head; while (prev != tail) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return {tail, head}; } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* new_head = new ListNode(0, head); ListNode* cur = new_head; while (cur) { ListNode* tail = cur; for (int i = 0; i < k; ++i) { tail = tail->next; if (tail == nullptr) return new_head->next; } auto p = reverseList(cur->next, tail); head = p.first; tail = p.second; cur->next = head; cur = tail; } return new_head->next; }