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 <= 100
• l1 和 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^5
• pos 为 -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 - 相交的起始节点的值。如果不存在相交节点，这一值为 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 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= 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] == 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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= 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^4
• Node.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^5
• pos 的值为 -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 <= 3000
• 0 <= key <= 10000
• 0 <= 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. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

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

对链表进行插入排序。

示例 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.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[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]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= 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]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= 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;
}