142.环形链表2(返回链表开始入环的第一个节点)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow=head,*fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow ==fast)
        {
            ListNode* meet=slow;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

第一种方法是有点巧妙在里面的，当fast指针与slow指针相遇时，这个相遇点meet到环起始位置的距离等于head指针到环起始点的距离，也就是等于L。

当相遇时，slow走的路程：L+N ，fast走的路程：L+xC+N
根据题目fast走的路程时slow的两倍。
2（L+N ）=L+xC+N
化简为 L=x*C-N
假设没有套圈，也就是x为0时L=C-N。即使套圈了相对位置也是一样的，所以L=C-N

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow=head,*fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow ==fast)
        {
            ListNode* meet=slow;
            ListNode* newHead=meet->next;
            meet->next=NULL;

            //判断是否为相交链表
            int lenA=1;
            int lenB=1;
            ListNode* curA=head;
            ListNode* curB=newHead;
            while(curA->next)
            {
                curA=curA->next;
                lenA++;
            }
            while(curB->next)
            {
                curB=curB->next;
                lenB++;
            }
           
            //是相交链表然后找相交节点
            int gap=abs(lenA-lenB);
            ListNode* longList=head,*shortList=newHead;
            if(lenA<lenB)
            {
                longList=newHead;
                shortList=head;
            }
            while(gap--)
            {
                longList=longList->next;
            }
            while(longList!=shortList)
            {
                longList=longList->next;
                shortList=shortList->next;
            }
            return shortList;

        }
    }
    return NULL;
    
}

这个就比较常规了，用到了找相交节点的知识。

先找到slow和fast相遇的节点meet。然后把这个环形链表给分割开来，创建了一个临时变量存储meet的下一个节点，并把meet的next指针置为空，这样就这个环就断开了。
然后就可以用返回相交链表的方法做了。
首先要先判断这两个链表是否相交。两个链表从头遍历到尾。其实这里肯定时相交的，这个步骤主要是为了求两条链表的长度。

求两个链表的长度，并求两个链表的长度差。让lenA-lenB因为不知道a长还是b长所以用abs求绝对值。要是按普通情况就要分情况a长一种情况b长一种情况，这种太麻烦。所以让A链表为长链表让B链表为短链标。如果B的长度>A的长度就让B链表为长链表A链表为短链表。
用while循环长度差gap次，让长链表和短链表一样长。然后遍历，如果长链表和短链表相同就停，并且返回任意一个这就是相交的节点。