LeetCode | 链表相关算法总结

这里总结一下常见的与链表有关的算法。

链表成环的各种问题

判断一个单链表是否存在环

这个思路比较简单,用 两个指针代表快、慢指针,然后从头指针开始,快指针一次前进两个结点,慢指针一次前进一个结点,则如果两个指针相遇(相等),则一定有环。若两指针不相遇,则 fast 指针遇到空指针后便结束循环。

  • 扩展:这种快、慢指针的思路还可用于找到无环链表的中间元素,当快指针到尾部时,慢指针正好到中间元素的位置。可用于链表的归并排序。

  • 扩展:这种两个指针的思路还可以用于寻找链表的第k个结点,思路同上。

对应:LeetCode 141 - Linked List Cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
return true;
}
return false;
}
};

若存在环,求环的长度

此处有定理I: 两指针(fast和slow)从第一次碰撞点出发到第二次碰撞所走的长度即为环的长度。

链表成环的情况

若存在环,求环的入口(连接点)

此处有定理II:第一次碰撞点到环的入口的距离,等于头指针到环的入口的距离。因此,分别从头指针和碰撞点遍历链表,第一次相遇的点即为换的入口(连接点)。

证明如下:
设单链表的总长度为L,头结点到环入口的距离为a,环入口到快慢指针相遇的结点距离为x,环的长度为r,慢指针总共走了s步,则快指针走了2s步。并且,快指针要追赶上慢指针,在环内的圈数n >= 1;因此我们可以列出式子:

$$s = a + x$$
$$2s = a + nr + x$$
$$=> a = nr - x = (n-1)r + y$$

由上式可知成立。
对应:LeetCode 142 - Linked List Cycle II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
ListNode *q = head;
while(q != slow) {
q = q->next;
slow = slow->next;
}
return q;
}
}
return nullptr;
}
};

链表相交的各种问题

如何判断链表相交,若相交则找到第一个交点

Question:给出两个单向链表的头指针,而两个链表都可能带环,判断这两个链表是否相交,并且给出他们相交的第一个节点。

思路:

首先根据上边的算法判断链表是否成环。

第一种情况:两个链表都不成环
思路1:将其中一个链表首尾相连,判断另一个链表是否存在环,如果存在,则两个链表相交,且找出来的环入口点即为相交的第一个点。
思路2:若如果两个不成环的链表相交,那么两个链表从相交点到尾结点都是相同的结点。首先先遍历两个链表,记录下两个链表的长度(长链表a,短链表b)。然后先让长链表移动a-b长度,然后两链表开始同步前进,相遇的第一个点即为环的第一个交点。

    A:          a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗            
    B:     b1 → b2 → b3

对应:LeetCode 160 - Intersection of Two Linked Lists

第二种情况:两个链表都成环

不可能的情况:一个有环,一个没有环

很好想的,如果两个链表一个有环,一个无环的话,那么它们不可能相交。

文章目录
  1. 1. 链表成环的各种问题
    1. 1.1. 判断一个单链表是否存在环
    2. 1.2. 若存在环,求环的长度
    3. 1.3. 若存在环,求环的入口(连接点)
  2. 2. 链表相交的各种问题
    1. 2.1. 如何判断链表相交,若相交则找到第一个交点