我的开源
『 代码随想录 』 双指针 - 链表篇
双指针 - 链表篇
1 合并两个链表
合并两个链表的题目本质是将两个有序链表进行合并;
-
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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均按 非递减顺序 排列
- 两个链表的节点数目范围是
这一题的重点思路是依靠双指针同时遍历l1与l2两条链表, 并维护一个哨兵节点, 将两个指针遍历的节点依靠大小判断挂在哨兵节点后;
当某条节点遍历完了之后循环则结束, 说明该链表已经没有多余的节点了, 只需要将剩余的有节点的链表的剩余部分继续往后挂即可;
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *sentinel = new ListNode();
ListNode *p = sentinel;
while(list1 && list2){
if(list1->val<list2->val) p->next = list1, list1 = list1->next;
else p->next = list2, list2 = list2->next;
p = p->next;
}
if(list1) p->next = list1;
if(list2) p->next = list2;
return sentinel->next;
}
};
2 分隔链表
-
给你一个链表的头节点
head和一个特定值x，请你对链表进行分隔，使得所有 小于x的节点都出现在 大于或等于x的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]示例 2：
输入：head = [2,1], x = 2 输出：[1,2]提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
- 链表中节点的数目在范围
该题的思路与题1类似, 只不过我们需要逆向的思维, 在题1中, 我们需要通过对应的规矩, 将两个链表合为同一条链表, 而这题的思路为:
- 将链表按照规则分为两个链表
- 将两个链表合为一个链表
若CSDN无法显示请点击此处
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *smaller = new ListNode();
ListNode *bigger = new ListNode();
ListNode *sp = smaller;
ListNode *bp = bigger;
while(head){
if(head->val>=x){
bp->next = head;
bp = bp->next;
}else{
sp->next = head;
sp = sp->next;
}
head = head->next;
}
bp->next = nullptr;
sp->next = bigger->next;
return smaller->next;
}
};
3 合并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
该题思路与 ==题一== 类似, 将若干个链表按照规则合为同一个链表, 但唯一不同的是, ==题一== 要求将两个链表合为一个链表, 我们能知道需要几个指针, 但是当存在K个链表时, 我们无法知道应该使用几个指针, 使用BF解法又过于暴力不优雅;
那么最优雅的方式是引入一个优先级队列, C++的优先级队列本质上就是一个堆, 我们需要创建一个小根堆, 每次头部取出的数据为最小的数据才能将K个链表合为一个链表, 优先级队列只存储每个链表的头结点, 这样优先级队列里只需要存储K个节点;
由于链表是链式结构, 在取出节点时只需要取出堆顶的节点, 并弹出链接至哨兵节点后的链表, 最后将这个节点的next节点再次push进优先级队列即可, 由于是小根堆, 他将根据规则自行维护堆的大小排布, 保持其顶部是当前最小的;
当链表为nullptr时说明链表已经遍历完毕, pop弹出之后可以不用再重新压入;
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *sentinel = new ListNode();
ListNode *p = sentinel;
auto cmp = [](ListNode *a, ListNode *b){
return a->val>b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for(int i = 0;i<lists.size();++i){
if(lists[i])
pq.push(lists[i]);
}
while(!pq.empty()){
ListNode *tmp = pq.top();
p->next = tmp;
pq.pop();
tmp = tmp->next;
if(tmp)
pq.push(tmp);
p = p->next;
}
return sentinel->next;
}
};
4 删除链表的倒数第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个节点, 当我们需要找到第n个节点时, 只需要使用两个指针, 指针fast先向走n步, 随后指针slow从头部与指针fast同时向后循环走一步, 直至fast触碰至nullptr则说明slow指针当前指向的是倒数第n个节点;
这是找到第n个节点的演示, 但我们实际上需要删除第n个节点, 因此由于是单链表, 我们无法在slow处于第n个节点时删除slow所在的节点, 因此我们需要找到倒数第n+1个节点, 而正常情况下, 若是链表节点只有1个, 而我们正好需要找倒数第一个节点, 那么fast需要走1+1步, 那么此时就会造成越界;
假设存在五个节点, 需要删除倒数第五个节点(如下图演示);
而我们若是引入了哨兵节点, 那么总长度则会是len+1, 那么则不会出现越界;
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 删除链表的倒数第n个节点
// 1) 找到链表的倒数第n+1个节点 - fast走n+1 步
ListNode *dummy = new ListNode();
dummy->next = head;
ListNode *fast = dummy;
int fastSteps = n+1;
while(fastSteps--){
fast = fast->next;
}
ListNode *slow = dummy;
while(fast){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};
5 链表的中间节点
-
给你单链表的头结点
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 ，返回第二个结点。
该题的思路, 实际上就是简单的快慢指针;
假设两个指针同时向后走, 快指针走两步, 慢指针走一步, 当快指针走到终点时, 慢指针一定在半路;
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *fast = head, *slow = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
6 环形链表 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 解释：链表中没有环。
该题环形链表与 ==环形链表I== 不同的是, 该题在判断链表相交后, 还需要正确的返回链表相交所在的节点;
对应的解题思路为, 使用快慢指针来定位快指针和慢指针的相交位置, 随后将其中一个指针置为链表原点位置, 两个指针同时向后遍历, 直至相遇, 所相遇的位置即为链表的环起点;
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 1) 找交点
ListNode *fast = head;
ListNode *slow = head;
while(fast&&fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
slow = head;
break;
}
}
if(!fast || !fast->next) return nullptr;
// 2) 同步找起点
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
// 3) 相交位置即为起点
return slow;
}
};
7 判断链表是否相交
-
给你两个单链表的头节点
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 。
本题的思路, 是通过两个指针在两条链表的头部同步进行遍历, 设指针为pa与pb, pa指针于A链表在遍历至nullptr节点时, 将其重新至于B链表的头部重新向后遍历, pb也是如此, 从链表B开始向后进行遍历, 遍历至nullptr空指针时, 将其重新至于A链表的头部, 随后继续向后遍历;
为什么这种走法能够明确的找到链表是否相交与相交的节点位置;
我们设A链表的长度为x, B链表的长度为y, 那么两个指针所走的距离是一致的, 由于链表不相交, 必然两个指针会在对方的nullptr终止;
当若是两个链表存相交的情况, 我们设不想交的部分, A, B链表的长度分别为x与y, 相交部分的链表长度为z;
那么两个指针分别要走的距离都为x+y+z, 由于两个链表共享z的长度, 那么实际会相遇的位置是z部分的头部, 那么判断链表是否相等即可判断其是否相交;
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA;
ListNode *p2 = headB;
while(p1!=p2){
if(p1 == nullptr) p1 = headB;
else p1 = p1->next;
if(p2 == nullptr) p2 = headA;
else p2 = p2->next;
}
return p1;
}
};
8 环形链表 I
-
给你一个链表的头节点
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 解释：链表中没有环。
该题的解题思路在 ==第六题== 中已经实践, 即单纯的判断链表是否带环, 只需要使用快慢指针, 快指针每次走两步, 慢指针每次走一步, 当链表存环时, 由于快指针的路程是慢指针的2倍, 因此必然快指针会在某处套圈慢指针;
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = fast;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow) return true;
}
return false;
}
};
9 LCR 训练计划 II
-
给定一个头节点为
head的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第cnt个训练项目编号。示例 1：
输入：head = [2,4,7,8], cnt = 1 输出：8提示：
1 <= head.length <= 1000 <= head[i] <= 1001 <= cnt <= head.length
本题的解题思路与 ==题4== 类似, 解题思路不再赘述, ==第四题== 是删除第
N个节点, 那么需要找到倒数第n+1个节点, 该题只需要找到第n个节点即可;class Solution { public: ListNode* trainingPlan(ListNode* head, int cnt) { ListNode *fast = head; ListNode *slow = head; while(cnt--) fast = fast->next; while(fast) slow = slow->next, fast = fast->next; return slow; } };