单链表的解题套路
01 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-two-sorted-lists著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
使用 while 循环每次比较 l1->val 和 l2->val 的大小，将较小的节点接在结果链表后。
代码中还使用了虚拟头节点，有了虚拟头节点这个占位符，可以避免处理空指针的情况。
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list2 == nullptr)
return list1;
if (list1 == nullptr)
return list2;
ListNode* dummay = new ListNode(-101);
ListNode* cur = dummay;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = (list1 == nullptr) ? list2 : list1;
return dummay->next;
}
02 合并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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
01 方法一：顺序合并
定义一个空的节点，每次和数组中的链表进行合并，每次都是两条链表合并。可以使用上一题的代码。
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr)
return list2;
if (list2 == nullptr)
return list1;
ListNode* dummay = new ListNode(-1);
ListNode* cur = dummary;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2->next;
list2 = list2->next;
}
cur = cur->next;
}
return dummay->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return nullptr;
}
if (lists.size() == 1)
return lists[0];
ListNode* ans = nullptr;
for (auto list : lists)
ans = mergeTwoLists(ans, list);
return ans;
}
02 方法二：分治合并
- 将
k个链表配对并将同一对中的链表合并； - 第一轮合并后，
k个链表被合并成了k / 2个链表，平均长度为2n / k，然后是k / 4个链表，k / 8个链表等； - 重复这一过程，直到得到最终的有序数组。
代码如下：
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr)
return list2;
if (list2 == nullptr)
return list1;
ListNode* dummay = new ListNode(-1);
ListNode* cur = dummary;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2->next;
list2 = list2->next;
}
cur = cur->next;
}
return dummay->next;
}
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
if (left == right)
return lists[left];
if (left > right)
return nullptr;
int mid = (left + right) >> 1;
return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() -1);
}
03 方法三：优先级队列
将链表节点放入一个小根堆，就可以每次获得 k 个 节点中的最小节点。维护当前每个链表没有被合并的元素最前面一个，每次从中选取值最小的一个，合并到答案中即可。
struct cmp {
bool operator()(ListNode* list1, ListNode* list2) {
return list1->val > list2->val;
}
};
ListNode* mergeKList(vector<ListNode*>& lists) {
if (list.empty())
return nullptr;
ListNode* dummay = new ListNode(-1);
ListNode* cur = dummay;
// 优先队列，最小堆
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
// 将 k 个链表的头节点加入最小堆
for (auto list : lists) {
if (list)
pq.push(list);
}
while (!pq.empty()) {
// 获取最小节点，放入结果链表中
ListNode* tmp = pq.top();
pq.pop();
cur->next = tmp;
// 如果该条链表没有到终点，将下一个链表放入最小堆
if (tmp->next)
pq.push(tmp->next);
cur = cur->next;
}
}
03 返回链表的倒数第 K 个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
使用双指针，先让快指针向前移动 k 个位置。然后快慢指针一起向前移动，当 fast == nullptr，返回 slow 即可。
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* fast = head;
for (int i = 0; i < k && fast != nullptr; ++i) {
fast = fast->next;
}
ListNode* slow = head;
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
04 删除链表的倒数第 N 个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
可以使用上一题思路，但是这题需要删除倒数第 k 个节点，所以需要找到它的前一个节点，此外，定义一个虚拟头节点，可以统一删除思路。比如链表共有 5 个基点，题目让你删除倒数第 5 个，按照逻辑，需要找到倒数第 6 个，但是第一个节点前面灭有节点了这就会出错。
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummay = new ListNode(-1);
dummay->next = head;
ListNode* fast = dummay;
fast = fast->next;
for (int i = 0; i < n && fast != nullptr; ++i) {
fast = fast->next;
}
ListNode* slow = dummay;
while (fast != nullptr) {
slow = slow->next;
fast = fast->next;
}
ListNode* tmp = slow->next;
slow->next = tmp->next;
delete tmp;
return dummay->next;
}
05 单链表的中点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
使用快慢指针，慢指针每次向前移动一位，快指针每次向前移动二位，当快指针移动到链表末尾，慢指针所指的位置就是链表的中点。如果链表长度为偶数，就会有两个中点，它会指向第二个中点节点。
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
06 环形链表-判断链表中是否有环
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
还是使用快慢指针。慢指针每次移动一步，快指针每次移动两步。如果快指针最终遇到空指针，说明链表中没有环；如果快慢指针相遇，则快指针至少超过了慢指针一圈，说明链表有环。
bool hasCycle(ListNode* head) {
if (head == nullptr)
return false;
ListNode* fast, *slow;
fast = slow = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
07 环形链表-链表的开始入环的第一个节点
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
先判断该链表是否有环。如果有环，让链表头指针和慢指针每次向前移动一位，如果两者相等，则该位置就是链表入环的第一个节点。
ListNode* detectCycle(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode* fast, *slow;
fast = slow = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {
while (head != slow) {
head = head->next;
slow = slow->next;
}
return head;
}
}
return nullptr;
}
08 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
输入：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 个节点。
输入：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 个节点。
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
01 方法一：哈希集合
使用哈希集合存储链表节点。
首先遍历链表 headA，并将每个节点存放在哈希集合。然后遍历 headB ，对于遍历到的每个节点，判断该节点是否在哈希集合中：
- 如果当前节点不在哈希集合中，则继续遍历下一个节点；
- 如果当前节点哈希集合中，则后面的节点都在哈希集合中，返回该节点
如果链表 headB 中的节点都不在哈希集合中，则两个链表不相交，返回 nullptr。
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
unordered_set<ListNode*> visited;
ListNode* temp = headA;
while (temp != nullptr) {
visited.insert(temp);
temp = temp->next;
}
temp = headB;
while (temp != nullptr) {
if (visited.count(temp) > 0)
return temp;
temp = temp->next;
}
return nullptr;
}
02 方法二：双指针
计算两个链表的长度，让长的链表先走 gap = lenA - lenB。这样可以使得两条链表按末尾对其的方式向前前进。然后让两个指针向后移动。如果 listA == listB。直接返回 listA or listB，如果到链表结尾，返回 nullptr 即可。
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* list1 = headA;
ListNode* list2 = headB;
int lenA = 0, lenB = 0;
while (list1 != nullptr) {
lenA++;
list1 = list1->next;
}
while (list2 != nullptr) {
lenB++;
list2 = list2->next;
}
list1 = headA;
list2 = headB;
if (lenA < lenB) {
swap(list1, list2);
swap(lenA, lenB);
}
int gap = lenA - lenB;
while (gap--)
list1 = list1->next;
while (list1 != nullptr && list2 != nullptr) {
if (list1 == list2) {
return list1;
} else {
list1 = list1->next;
list2 = list2->next;
}
}
return nullptr;
}
若有收获，就点个赞吧
0 人点赞
