双指针在链表上的操作
双指针的一个基础应用是链表的常见操作
1.双指针的思想是对逻辑组织上的两部分别进行维护
2.双指针并不意味着解决问题只用 2 个指针就够, 可能用到其他的关键指针
链表结构的一般定义
// 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) {}
};
21.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：输入：l1 = [], l2 = [] 输出：[]
示例 3：输入：l1 = [], l2 = [0] 输出：[0]
分析:
1.合并有序链表的操作关键操作是分别用两个指针维护当前列表 list1/list2 的指针 p1 和 p2, 然后再用一个指针维护合并的指针, 这个合并指针好像一个针线头一样, 把两条线穿起来
2.先处理 p1 和 p2 同时非空的场景, 然后再处理剩下的唯一的链表有剩余的场景
3.为了方便处理有链表为空的情况, 额外设置一个 dummy 节点, 返回 dummy->next
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
ListNode* p1 = list1;
ListNode* p2 = list2;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val < p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
if (p1 != nullptr) {
cur->next = p1;
}
if (p2 != nullptr) {
cur->next = p2;
}
return dummy->next;
}
};
3.这道题有个递归的写法, 待补充
86.分隔链表
给你一个链表的头节点 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]
分析:
1.新建两个链表, 一个是构建小于等于 x 的链表 small, 另一个是存放大于等于 x 的链表 large
2.依次遍历当前的链表, 如果小于 x, 那么用 small->next 连接到 cur, 然后 small 向后推一个到 cur, large 同理
3.末尾断开处理: 将 small 的最后一个连接到 large 上面, 串起来 small->next = largeHead->next; large->next 需要设置为 nullptr, 不然断不开
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* smallDummy = new ListNode(-1);
ListNode* largeDummy = new ListNode(-1);
ListNode* small = smallDummy;
ListNode* large = largeDummy;
ListNode* cur = head;
while (cur) {
if (cur->val < x) {
small->next = cur;
small = small->next;
} else {
large->next = cur;
large = large->next;
}
cur = cur->next;
}
small->next = largeDummy->next;
large->next = nullptr;
return smallDummy->next;
}
};
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 = [[]] 输出：[]
分析:
1.如果是合并 2 个升序链表, 我们可以维护两个指针去比较, 如果是 k 个链表, 则不太好比较
2.如果想维护 k 个链表里面的最小值, 那么需要引入一个小顶堆去找到最小节点, 来多少个链表我们都不管, 我们每次都取最小的那个节点: 每次取出来最小的那个节点, 然后链接到生成的链表的末尾, 看下后续还有无其他的节点, 有的话放入队列一起比较, 直到最后队列元素为空
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [] (ListNode* p1, ListNode* p2) {
return p2->val < p1->val;
};
// 采用一个按照值排序的有限队列
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
for (auto head: lists) {
if (head != nullptr) {
pq.push(head);
}
}
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (!pq.empty()) {
cur->next = pq.top();
pq.pop();
cur = cur->next;
if (cur->next != nullptr) {
pq.push(cur->next);
}
}
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
这道题也可也用分治法, 待补充
剑指向offer 22.链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
分析:
1.因为题目没有说明链表的长度, 因此常规情况下需要遍历2次, 第1次遍历找到链表长度例如n, 第2次遍历找到n-k个节点;
2.采用双指针的方法可以遍历1次链表找到倒数第k个节点: 假设链表长度为n, 找倒数第k个节点就是找正数n-k+1个节点
3.先用快指针从第1个节点走k步, 剩下n-k-1个节点没有遍历, 然后此时用慢指针开始从head出发遍历, 直到快指针遍历为空, 也就是快和慢都走了n-k步, 这时候慢指针走到了n-k+1的节点, 也就是倒数第k个节点;
4.假设节点是[1,2,3,4,5], 我们要找倒数第2个节点也就是4, 也就是正数第4=5-2+1个节点, 默认从1出发, 快指针走2步骤到3, 慢指针此时出发, 快指针再走3步到空, 慢指针走3步到4;
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* fast = head;
for (int i = 0; i < k; ++i) {
fast = fast->next;
}
ListNode* slow = head;
while (fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
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]
分析:
1.如果要删除倒数第 N 个节点, 也就是删除正数 nums-N+1 个节点, 为了删除 nums-N+1 的节点, 我们需要指针指向删除目标节点的前一个节点, 即正数 nums-N 个节点, 也就是倒数 N+1 个节点
2.一种方法是遍历一遍找到 N 等于几, 然后再遍历一遍执行删除操作
3.更方便的一种方式是先让 fast 先正好走到我们想要 slow 停下来的节点, 也就是待删除的节点的前一个节点, 然后再快慢同速度一起走, 直到 fast 为空, 这时候 slow 停下来的节点就是正数 nums-N 个节点; 其实我们脑洞开一点, 就好比等价于有另一个指针 (fast) 先执行倒着走一样, 它能先帮我们找到那个前一个节点
4.假设 [1,2,3,4,5], n=2, 为了防止空指针出现, 比如 5 个节点删除倒数第 5 个, 要用 dummy 去避免空指针; fast 指针可以从 head 开始, 然后 slow 指针多走一步从 dummy 开始, 这样就能直接达到走到待删除节点的下一个节点的效果; 增加 dummy 得到 [d,1,2,3,4,5], 所以, fast 从 1 出发走 2 步到 3, 然后走 3 步到空指针, slow 从 dummy 出发走 3 步到 3, 也就是 4 的前1个节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1, head);
// 举例 [d,1,2,3,4,5], n=2, fast 停在3, slow 最终停在3
ListNode* slow = dummy; // slow 从 dummy 出发, 能够多走一步, 保证 slow 最终停在待删除节点前面
ListNode* fast = head; // fast 从 head 出发
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
876.链表的中间节点
给定一个头结点为 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 之间。
分析:
1.快指针一次走 2 步, 慢指针一次走 1 步
2.[1,2,3,4,5,6], 快指针到 3, 慢指针到 2, 快指针到 5, 慢指针到 3, 快指针到 null, 慢指针到 4; return 4
3.[1,2,3,4,5], 快指针到 3, 慢指针到 2, 快指针到 5, 慢指针到 3; return 3
4.因此能完成走快指针走2的基础的条件是 while (fast && fast->next)
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
141.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。示例 1：输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
分析:
1.快慢指针有相遇, 那么就有环, 否则就没有环
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
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 解释：链表中没有环。
分析:
1.需要分析下相遇点有什么特点, 我们仍然采用快慢指针的方式来看, 起点快慢指针都指向非空的 head, 假设 slow 走了 k 步之后, fast 和 slow 相遇了, slow 走 k 步, 那么 fast 走 2k 步; fast 比 slow 多走出的 k 步是在环里面转圈, 所以这个相遇时候慢指针走过的 k 步的 k 的值正好就是环长度的 [整数倍]
2.假设 [相遇点] 距离 [环起点] 为 m , 原始头节点距离 [环起点] 为 k - m , fast 如果继续往前走 k - m 步到达环的起点, 但是我们不知道这个 m 是多少; 这里我们知道, 相遇之后原始头结点距离 [环起点] 距离 == [相遇点] 距离 [环起点] 继续走距离都是 k - m; 所以我们让快慢指针第一次相遇的时候, 让快慢指针的任意一个重新指向 head, 比如 slow 重新指向 head, 然后 slow 和 fast 指针同速前进 (每次走1步), (经过 k - m 步) 然后它俩一定相遇, 相遇的地方就是环的起点
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
// 假设 [相遇点] 距离 [环起点] 为 m , 原始头节点距离 [环起点] 为 k - m , fast 如果继续往前走 k - m 步到达环的起点, 我们不知道这个 m 是多少;
// 相遇之后原始头结点距离 [环起点] 距离 == [相遇点] 距离 [环起点] 继续走距离都是 k - m;
// 我们让快慢指针第一次相遇的时候, 让快慢指针的任意一个重新指向 head, 比如 slow 重新指向 head, 然后 slow 和 fast 指针同速前进 (每次走1步), (经过 k - m 步) 然后它俩一定相遇, 相遇的地方就是环的起点;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
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 输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。这两个链表不相交，因此返回 null 。
你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
分析:
1.这个题如果直接看了答案只能感觉很巧妙, 但是不看答案又想不出来这个巧妙的答案, 先给出比较基础的方法: 用一个 hashset 保存 headA 下的所有节点, 然后和另一个链表逐个对比就能找到公共节点, 但是需要额外的空间
2.需要充分利用”相交”这个信息, 一种解决的方式是, 将两条链表按照前后两种不同的顺序拼接在一起, 例如如下的两条链表公共节点是 c1
a1->a2->c1->c2
b1->b2->b3->c1->c2
拼接之后得到两条长度相同的链表
a1->a2->c1->c2->b1->b2->b3->c1->c2
b1->b2->b3->c1->c2->a1->a2->c1->c2
这样我们同时遍历这两个链表, 找到的第一个相同的节点就是 c1 就是链表交点
3.在实际遍历的时候, 可以想象这两个链表已经被拼接起来, 但不实际地去开辟额外空间, 只在原来的两条链表上面走
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* pa = headA;
ListNode* pb = headB;
while (pa != pb) {
if (pa) {
pa = pa -> next;
} else {
// 将pa链接在b的开头
pa = headB;
}
if (pb) {
pb = pb -> next;
} else {
// 将pb链接在b的开头
pb = headA;
}
}
return pa;
}
};
725.分割链表
给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。返回一个由上述 k 部分组成的数组。
示例 1：输入：head = [1,2,3], k = 5 输出：[[1],[2],[3],[],[]]
解释：第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。示例 2：输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3 输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。
分析:
1.题目要求排在前面的部分要更长, 算一下
总长度是10 % 3 = 1, 所以只给前 1 个part(part0)的宽度+1
总长度是11 % 3 = 2, 所以只给前 2 个part(part0, part1)宽度+1
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* head, int k) {
int len = 0;
ListNode* tmp = head;
while (tmp != nullptr) {
tmp = tmp->next;
++len;
}
int defaultSize = len / k;
int extraSize = len % k;
vector<ListNode*> parts(k, nullptr);
ListNode* cur = head;
for (int i = 0; i < k && cur != nullptr; ++i) {
parts[i] = cur;
int partSize = defaultSize;
if (i < extraSize) {
++partSize;
}
for (int j = 1; j < partSize; ++j) {
cur = cur->next;
}
ListNode* next = cur->next;
cur->next = nullptr;
cur = next;
}
return parts;
}
};
707.设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
分析:
1.leetcode 平台已经实现了默认的 ListNode 结构
2.添加和删除时, 需要判断各种边界条件再做操作
class MyLinkedList {
private:
ListNode* head;
int size;
public:
MyLinkedList() {
this->head = new ListNode(0);
this->size = 0;
}
int get(int index) {
if (index < 0 || index >= size)
return -1;
ListNode* cur = head;
for (int i = 0; i <= index; ++i) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val) {
if (index > size)
return;
++size;
ListNode* pre = head;
for (int i = 0; i < index; ++i) {
pre = pre->next;
}
ListNode* newNode = new ListNode(val);
newNode->next = pre->next;
pre->next = newNode;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size)
return;
--size;
ListNode* pre = head;
for (int i = 0; i < index; ++i) {
pre = pre->next;
}
ListNode* p = pre->next;
pre->next = pre->next->next;
delete p;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
转载请注明来源, from goldandrabbit.github.io
