leetcode141.环形链表，142环形链表ii

问题描述

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

题目链接：环形链表1

示例

提示

  链表中节点的数目范围是 [0, 104]
  -105 <= Node.val <= 105
  pos 为 -1 或者链表中的一个 有效索引 。

具体思路

思路一

环形链表1
1、slow和fast一定会相遇吗？
一定会，fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N
slow进环以后，fast开始追击slow，slow每走1步，fast每走2步，他们之间距离缩小1。
N N-1 N-2 N-3 N-4 … 2 1 0

2、slow走1步，fast走n(3/4/5…)步可以吗？(n>2)
不一定，fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N
slow进环以后，fast开始追击slow，slow每走1步，fast每走3步，他们之间距离缩小2。
N N-2 N-4 N-6 … 4 2 0
N是偶数就会相遇。N是奇数就会错过，会进入新一轮的追击，slow和fast的距离变成C-1（假设C是环的长度）
如果C-1是偶数那么下一轮可以追上
如果C-1是奇数那么永远追不上

代码实现

//思路1
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head;
    struct ListNode* fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        return true;
    }

    return false;
}

问题描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

题目链接：环形链表2

具体思路

思路一

转换为相交链表的问题，将meetNext=meet->next，meet->next=NULL。然后使用相交链表的问题求解相交的交点

思路二

环形链表2
fast走的路程是slow的2倍
假设：链表头–环入口点距离：L
环入口点–距离点距离:X
环的长度：C

slow走的路程是多少：L+X -> 分析，有没有可能slow进环转了几圈才追上？不可能！1圈之内，fast必然追上slow，因为他们之间距离每次缩小1，不会错过，slow走1圈，fast都走了2圈了，肯定追上了。

fast走的路程是多少：L+nC+X

2*(L+X)=L+nC+X
L+X=nC
L=nC-X
n是slow进环前，fast在环里面转的圈数

所以一个指针从相遇点走，一个指针从链表头开始走，他们会在入口点相遇

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head;
    struct ListNode* fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            struct ListNode* meet=slow;
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}