leetcode 141. Linked List Cycle 、 142. Linked List Cycle II

判断链表有环，环的入口结点，环的长度

1.判断有环：

快慢指针，一个移动一次，一个移动两次

2.环的入口结点：

相遇的结点不一定是入口节点，所以y表示入口节点到相遇节点的距离

n是环的个数

w + n + y = 2 (w + y)

　　 经过化简，我们可以得到：w  = n - y;

https://www.cnblogs.com/zhuzhenwei918/p/7491892.html

3.环的长度：

从入口结点或者相遇的结点移动到下一次再碰到这个结点计数

https://blog.csdn.net/jyy305/article/details/75267969

141. Linked List Cycle

使用快慢指针，一个一次滑动一次，一个一次滑动两次。

如果只是判断有没有环，初始化可以不两个都初始化到head，但为了方便和找入口节点那个题的记忆，都初始化为head。

两个都初始化为head，就不能先把if(p1 == p2)放在while循环的开始，要放在迭代之后。

class Solution {

public:

    bool hasCycle(ListNode *head) {

        if(head == NULL)

            return false;

        //ListNode* p1 = head,p2 = head;

        ListNode* p1 = head;

        ListNode* p2 = head;

        while(p2 != NULL && p2->next != NULL){

            p1 = p1->next;

            p2 = p2->next->next;

            if(p1 == p2)

                return true;

        }

        return false;

    }

};

142. Linked List Cycle II

两个指针初始化必须初始化在head的地方，这样才能使用后面推导的公式https://www.cnblogs.com/ymjyqsx/p/9568129.html

在head申明一个新的节点，一个一个滑动，然后p1也是一个一个滑动，相遇的节点就是入口节点

head->next == NULL是为了避免[1]这种情况

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

        if(head == NULL)

            return NULL;

        if(head->next == NULL)

            return NULL;

        ListNode* p1 = head;

        ListNode* p2 = head;

        while(p2 != NULL && p2->next != NULL){

            p1 = p1->next;

            p2 = p2->next->next;

            if(p1 == p2)

                break;

        }

        if(p1 != p2){

            return NULL;

        }

        ListNode* p3 = head;

        while(p1 != p3){

            p1 = p1->next;

            p3 = p3->next;

        }

        return p1;

    }

};

leetcode 141. Linked List Cycle 、 142. Linked List Cycle II的相关教程结束。