环检测

Posted on   |   In   |  

环检测问题

环检测

环检测问题是数学中一个重要的问题。
环检测
重点看龟兔算法
这篇文章给出了详细的说明:http://blog.csdn.net/lanceleng/article/details/8707135

Linked List Cycle

Given a linked list, determine if it has a cycle in it.
给定一个链表，如何判断出它是否有环。

利用龟兔算法，也就是快慢指针法，如果最后两个指针相等，一定有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *p2 = head;
    struct ListNode *p = head;
    if(head == NULL || head->next == NULL)
    return false;
    while(p2 != NULL && p2->next != NULL){
        p2 = p2->next->next;
        p = p->next;
        if (p == p2) break;
    }
    return (p == p2);
}

Linked List Cycle ii

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
判断环的起点:
环的起点
图片摘自http://www.cnblogs.com/hiddenfox/p/3408931.html
现证明:X是链表的起点，Y是环的起点，Z是相遇点，L是环的长度

两个指针相遇时，快指针走的距离为$ a+b+n*L(n >= 1) $

慢指针走的距离为:$ a+b + m*L $,

那么$2(a+b+mL) = (a+b+nL)$,

所以得到的等式是$a =(n-2m)*L - b$;
上面的等式意味着,当一个指针从起点出发时，另一个指针从Z出发时，他们的相遇点一定是环的起点

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
30
31
/**
 * 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) {
        if(head == NULL || head->next == NULL)  return NULL;
        ListNode *slow = head;
        ListNode *fast = head;
        
        do{
            if(fast == NULL || fast->next == NULL) return NULL;
            slow = slow->next;
            fast = fast->next->next;
        }while(slow != fast);
        
        if(fast != slow)    return NULL;
        
        slow = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

还有一种http://fisherlei.blogspot.com/2013/11/leetcode-linked-list-cycle-ii-solution.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode *detectCycle(ListNode *head) {
    ListNode * first = head;
    ListNode * second = head;
    
    while(first != NULL && second != NULL){
        first = first->next;
        second = second->next;
        if(second != NULL)
        second = second->next;
        if(first == second)
            break;
    }
    if(second == NULL) return NULL;
         
    // 一起往下走X步，就找到节点了。
    first = head;
    while(first!=second){
        first = first->next;
        second = second->next;
    }
         
    return second;
}