Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

链表-02

双指针技巧

我们之前在数组中引入了双指针技巧,先做一个简要回顾,有两种使用双指针的情景:

  1. 两个指针从不同位置出发:一个从头部开始,另一个从尾部开始;
  2. 两个指针以不同速度移动:一个指针快一些,另一个指针慢一些;

对于单链表,由于我们只能在一个方向上遍历链表,所以第一种情景可能无法工作。但是第二种指针,即快慢指针是非常有用的技巧。

以下我们将重点讨论链表中的快慢指针问题,并告诉你如何解决这类问题。

链表中的双指针

首先从一个经典问题开始:

给定一个链表,判断链表中是否有环。

熟悉哈希表的可能已经使用哈希表提出了解决方案。但是,使用双指针技巧有一个更有效的解决方案。

想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

这正是在链表中使用两个速度不同的指针时会遇到的情况:

  1. 如果没环,快指针将优先抵达链表尾部。
  2. 如果有环,快指针最终将会追上慢指针。

所以剩下的问题是:这两个指针的适当速度应该是多少?

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

我们用题目来展现问题:

题目:环形链表

给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果 pos-1,则在该链表中没有环。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:使用 O(1) 内存解决此问题,即空间复杂度为O(1)

个人理解
采用刚了解到的快慢指针法来判断链表中是否有环即可。
定义快慢指针,让快指针一次走两部,慢指针一次走一步:如果快指针抵达终点,说明链表内部没有环;如果快指针追上了慢指针,则说明链表内部有环存在。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast{head}, *slow{head}; // 定义双指针
if(head == nullptr) return false; // 特判
while(fast != nullptr && fast -> next != nullptr){ // 判断是否到头
fast = fast -> next -> next; // 走两步
slow = slow -> next; // 走一步
if(fast == slow) return true; // 相遇则为环
}
return false; // 否则到尽头无环
}
};

题目:环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos-1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

个人理解
查看示例的内容我们可以得知,这次要返回的是环的点,所以我们还是采用双指针法来解决。
官方称之为:Floyd 算法,如果链表中有环存在,快指针必然会追上慢指针,在此我们设定,起点为 A,环点为 B,追逐点为 C,令:
A->B 为 x
B->C 为 y
C->B 为 z
慢指针走的路线为:x + y
快指针走的路线为:x + y + z + y
又因:快指针 = 慢指针 * 2
可得:x = z
即我们想要的 B 点,其实就是 x 的长度,所以在相遇后,将慢指针放回起点,两个指针继续走,再次相遇就是 B 点相遇了。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast{head}, *slow{head}; // 定义双指针
if(head == nullptr) return nullptr; // 特判
while(fast != nullptr && fast -> next != nullptr){ // 判断是否到头
fast = fast -> next -> next; // 走两步
slow = slow -> next; // 走一步
if(fast == slow){ // 相遇则为环
slow = head;
while(fast != slow){ // 将slow放回头部,继续走
slow = slow -> next; // 走一步
fast = fast -> next; // 走一步
}
return slow; // 相遇返回slow即可
}
}
return nullptr; // 否则到尽头无环
}
};

题目:相交链表

编写一个程序,找到两个单链表相交的起始节点。
如下两个链表:

在节点C1开始相交。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,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。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

个人理解
利用两个链表总路程一样,进行遍历:
分别定义两个指针在两个链表头部,每次走一步,走完自己路程去走另一个链表内容,最终步数均为 x + y
如果相遇则结束,相遇点即为交点,最后也同时抵达结尾 null,最终返回 null。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a{headA}, *b{headB}; // 定义两个指针分别在两个链表头部
if(headA == nullptr || headB == nullptr)
return nullptr; // 都为空则肯定没交点
while(a != b){ // 总路程是一样的,都是 a + all + b
if(a == nullptr) a = headB; // a到头交换到B链表头部
else a = a -> next; // 走一步
if(b == nullptr) b = headA; // b到头交换到A链表头部
else b = b -> next; // 走一步
} // 两个同时到达结尾 null,结束循环,返回null
return a;
}
};

题目:删除链表的倒数第 N 个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头节点 1。

示例:

1
2
给定一个链表: 1->2->3->4->5, 和 n = 2
当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:给定的 n 保证是有效的

进阶:尝试使用一趟扫描实现

个人理解
采用双指针的另一种用法,还是同向移动,但是,一个指针先移动一定的距离,用作距离标定,随后开始步进,另一个指针联动
做法如下:

  1. 先定义一个哑节点放在头部
  2. 在哑节点位置定义两个指针
  3. 将一个指针先行 n+1 步
  4. 一起移动,知道先行指针到头
  5. 此时后指针就在要删除节点前
  6. 删除节点即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *header = new ListNode(0); // 定义一个哑节点
header -> next = head; // 将哑节点放在头部
ListNode *a{header},*b{header}; // 在哑节点位置放置两个指针
for(int i = 0; i < n+1; i++) b = b -> next; // 将 b 指针先移动 n+1 步
while(b){ // 将 b 指针移动到头,a 指针联动
a = a -> next;
b = b -> next;
}
a -> next = a -> next -> next; // a 这时候位置就在要删除节点前
return header -> next; // 返回 header->next 即可
}
};

小结 - 链表中的双指针

在这里,我们为你提供了一个模版,用于解决链表中的双指针问题。

模版如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 初始化快慢指针
ListNode* slow = head;
ListNode* fast = head;
/**
* 根据不同的问题更改条件
* 注意: 记得避免空指针错误
**/
while (slow && fast && fast->next) {
slow = slow->next; // 每次将慢指针移动一步
fast = fast->next->next; // 每次将快指针移动两步
if (slow == fast) { // 根据不同的问题更改条件
return true;
}
}
return false; // 更改返回值以适合特定问题

提示

它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点:

1.在调用 next 字段之前,始终检查节点是否为空:
获取空节点的下一个节点将导致空指针错误。例如,在我们运行 fast = fast.next.next 之前,需要检查 fast 和 fast.next 不为空。

2.仔细定义循环的结束条件:
运行几个示例,以确保你的结束条件不会导致无限循环。在定义结束条件时,你必须考虑我们的第一点提示。

复杂度分析

空间复杂度分析容易。如果只使用指针,而不使用任何其他额外的空间,那么空间复杂度将是 _O(1)_。但是,时间复杂度的分析比较困难。为了得到答案,我们需要分析运行循环的次数。

在前面的查找循环示例中,假设我们每次移动较快的指针 2 步,每次移动较慢的指针 1 步。

如果没有循环,快指针需要 N/2 次才能到达链表的末尾,其中 N 是链表的长度。
如果存在循环,则快指针需要 M 次才能赶上慢指针,其中 M 是列表中循环的长度。
显然,M <= N 。所以我们将循环运行 N 次。对于每次循环,我们只需要常量级的时间。因此,该算法的时间复杂度总共为 O(N)。

自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析,请考虑最糟糕的情况。

声明:本文为学习记录,不做商业用途,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~