141. Linked List Cycle

发表于 | 分类于 | |

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

题意：判断一个链表是否带环。

这是一道关于链表很经典的题目，解法其实跟跑操场（操场就是个环）原理很类似：A,B从同一起点开始一起跑，A跑得慢，B跑得快，那么B一定会在某个时刻跟A相遇（B比A跑快了一圈了）。

但是万一没有环呢？因为B跑得快，所以只要B还没到终点，A就肯定还没到终点。所以只需要判断跑得快得指针非空就行了。

一开始的代码就写错了，既判断了A又判断了B。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head)
            return false;
        ListNode *p1 = head;//跑得慢
        ListNode *p2 = head;//跑得快

        while (p1->next && p2->next->next)//这里p1错了，不需要管跑得慢的
        {
            p1 = p1->next;
            p2 = p2->next->next;
            if (p1 == p2)//类似跑操场，跑得快得肯定会追上跑得慢的，快一圈相遇
                return true;
        }
        return false;
    }
};

正确的代码如下：

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
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head)
    {
        if (!head)
            return false;
        ListNode *p1 = head;//跑得慢
        ListNode *p2 = head;//跑得快

        while (p2->next && p2->next->next)//只需要关注跑得快得到不到终点就行
        {
            p1 = p1->next;
            p2 = p2->next->next;
            if (p1 == p2)//类似跑操场，跑得快得肯定会追上跑得慢的，快一圈相遇
                return true;
        }
        return false;

    }
};