給定一個鏈表的頭節點 head ，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改 鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。
示例 2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。
示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

提示：

鏈表中節點的數目范圍在范圍 [0, 104] 內
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個有效索引

自解

十分暴力的解法
用一個新鏈表儲存所有鏈表的地址，依次遍歷所有待查找鏈表的節點，將其指向的地址與新鏈表中儲存的地址作比較。
能跑，但性能較差

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //哈希表
struct ListNode1 {
      struct ListNode *address;
      struct ListNode1 *next;
  };

struct ListNode1 HashTable;
struct ListNode1 *tail=NULL;
struct ListNode1* find(struct ListNode *temp)
{
    struct ListNode1* head=HashTable.next;
    while(head!=NULL)
    {
        if(temp->next==head->address)return head;
        head=head->next;
    }
    return NULL;
}

void insert(struct ListNode *temp)
{
    struct ListNode1* newnode=(struct ListNode1*)malloc(sizeof(struct ListNode1));
    newnode->address=temp;
    newnode->next=NULL;
    tail->next=newnode;
    tail=tail->next;
}

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode1 *temp=NULL;
    HashTable.address=NULL;
    HashTable.next=NULL;
    tail=&HashTable;
    while(head!=NULL)
    {
        if((temp=find(head))!=NULL)
        {
            return head->next;
        }
        insert(head);
        head=head->next;
    }
    return NULL;
} 

力扣解

仍然是使用快慢指針
靈佬寫的很清楚了
當快指針與慢指針在環中相遇時一共走了b步，設總頭節點到環的頭節點的節點數為a，環中的節點數為c,快指針在環中走了k圈
則2b-b=kc->b=kc(k是因為快指針一定是在節點中繞了k圈后才與慢指針相遇)
慢指針在從環節點頭開始走過的距離為：b-a->kc-a(代入b=kc),也就是說此時慢指針在節點中再走a步就能到達環節點頭
那我們讓總節點頭與慢指針同時動，兩者相交時必定就在環節點的頭

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 (fast == slow) { // 相遇
            while (slow != head) { // 再走 a 步
                slow = slow->next;
                head = head->next;
            }
            return slow;
        }
    }
    return NULL;
}

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/1999271/mei-xiang-ming-bai-yi-ge-shi-pin-jiang-t-nvsq/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

仿解

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head,*slow=head;
    while(fast&&fast->next)//等快慢指針相遇，若快指針遍歷到NULL代表無環，會退出循環直接返回NULL
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)//相遇
        {
            while(head!=slow)//總頭節點與慢指針同時動
            {
                head=head->next;
                slow=slow->next;
            }
            return head;//相遇后退出循環，此時相遇節點即為環節點的頭節點
        }
    }
    return NULL;
}