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

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

题意

判断一个链表是否有环

答案
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;
    while( slow && fast && fast->next )
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow) return true;
    }
    return false;
    }
};

思路

设置一个快指针一个慢指针,开始都指向头,快指针一次有两步,慢指针一次走一步,如果遇到了就是有环,没遇到就是没环.

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

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

大意

找出循环的开始节点

答案

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
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {    
        if (head == NULL || head->next == NULL) 
        {
            return NULL;
        }
        ListNode* slow =head;
        ListNode* fast =head;
        while(fast!=NULL&& fast->next!=NULL)
        {
            fast =fast->next->next;
            slow =slow->next;
            if(fast==slow)   // there is a cycle
            {
                while(head!=slow) // found the 相遇 location
                {
                    head=head->next;
                    slow=slow->next;
                } 
                return head;
            }
        }
        return NULL; // there has no cycle
    }
};

思路

需要推导,大意就是先快慢指针往前走,当相遇后,慢指针接着往前,头指针开始动,慢指针和头指针相遇的地方就是循环开始的地方.