环形链表

发表于 | 分类于 | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 4 分钟

题目

#141 Linked List Cycle

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

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

解题思路

常规的思路是使用哈希表，遍历链表检查哈希表中是否已有该元素，如果有就直接返回false，没有的话就将其存入哈希表。但是这样做的空间复杂度为O(n)，下面介绍一种空间复杂度为O(1)的算法。

双指针法

使用两个指针（快慢指针）遍历链表，快指针每次移动两步，慢指针只移动一步。如果快指针到达了链表尾，则表明没有环；而如果快指针追上了慢指针，则有环。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
        return false;
    }
    ListNode *fast = head->next;
    ListNode *slow = head;
    while (fast != slow) {
        if (!fast || !fast->next) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

进阶版

#142 Linked List Cycle Ⅱ

这道题不仅要判断是否有环，还要找出首次入环的位置。

解题思路

同样可以采取哈希表的方法，但要想在O(1)的空间复杂度内解决，还需要一些技巧。

先使用上述简化版的方法得到相遇点，于是整个图共有三个关键点：起始点，待求的入环点和使用快慢指针得到的相遇点，如下图所示：

graph

设各点间的距离如上图所示，于是我们可以得到距离间的数量关系：

由快指针的速率是慢指针的二倍，可得：

a+x+y+x = 2*(a+x)

化简，得

a = y

也就是说再使用两个速率相同的指针分别从起始点和相遇点运动，则它们会在待求点相遇。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode *detectCycle(ListNode *head) {
    if (!head || !head->next || !head->next->next) {
        return NULL;
    }
    ListNode *fast = head->next->next;
    ListNode *slow = head->next;
    while (fast != slow) {
        if (!fast || !fast->next) {
            return NULL;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    slow = head;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}