LeetCode 环形链表 II(C语言)

题目要求

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/linked-list-cycle-ii

在这里插入图片描述

分析

想找到入环的第一个结点那么遍历链表肯定是不行的，因为这是个循环链表，所以我们可以用双指针来解决这个问题。 一个快指针，一个慢指针在这个链表中循环，他们总会有相遇的时候，那么就可以利用这个相遇点来进行操作。 两个指针相遇的条件是快指针走两步，慢指针走一步，这个是固定的走法。（假设慢指针是p1，快指针是p2。） 假设快指针和慢指针都进入了圆环内，两个指针相隔的长度为N，如果是两个指针的步数只差一，差距就是N-1，N-2，N-3…0. 但如果是p1走一步，p2走三步，差距是2，N-2，N-4，N-6，如果N是一个偶数，那么差距逐渐会变为0，如果N是奇数，一圈的长度也是奇数，差距会变成-1，也就是p1被p2反超一圈，这样无论如何都不可能相遇了。所以这样的情况下是不一定能相遇。 就算p1走N步，p2走M步也是一样的。 所以我们让p1一次走一步，p2一次走两步。 回到我们这道题的分析，利用相遇点推导公式解决。 假设未进入圆环之前长度为L，圆环的长度为C，在圆环中相遇点与我们要找的第一个结点相距长度为X。

在这里插入图片描述

p2走的距离=2p1走的距离 我们再假设p1进入圆环之前p2再圆环中走了N圈(N>=1) p1走的距离：L+X p2走的距离；L+NC+X 2(L+X)=L+NC+X L+X=NC L=NC-X L=(N-1)*C+C-X 也就是说，两个一次只走一步的指针，其中一个再表头走，另一个再相遇点走，都会在第一个结点相遇。 知道这一点就容易解决这道题了，只要先找到他们的相遇点然后再让两个指针从表头和相遇点一步一步的走就能相遇了，虽然圆环中的指针可能会循环多次。

代码实现

Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *detectCycle(struct ListNode *head) {   
    struct ListNode *p1=head;//慢指针
    struct ListNode *p2=head;//快指针
    while(p2&&p2->next)//寻找快慢指针的相遇点
    {
        p1=p1->next;
        p2=p2->next->next;
        if(p1==p2)
        {
        	struct ListNode *cur = head;//从头出发的指针
            struct ListNode *next=p1;//从相遇点出发的指针
            while(cur != next)
            {
                cur=cur->next;
                next=next->next;
            }
            return cur；//找到相遇点后返回其中一个指针就可以了
        }
    }
    return NULL;
}