网站常用模块最新军事头条

题目链接：142.环形链表II

题目描述：

        给定一个链表的头节点  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 或者链表中的一个有效索引

思路：参考环形链表I ，依旧使用快慢指针解决

        参考环形链表I ，快慢指针一定会在环形链表中相遇。

        以示例1为例：

        head为链表的头结点，meet为快慢指针在环中的相遇点， 由图可以初步判断：

        meet到入环的初始结点的距离等于head到入环的初始结点的距离。

证明：相遇点到入环起始结点的距离 = 链表头结点到入环起始结点的距离

        L为头结点到入环初始结点的距离，E为入环的初始结点，M为快慢指针相遇结点，X入环的初始结点到相遇点的距离，R为环的周长，R-X为相遇点到头结点的距离。

        在快慢指针相遇时，fast所走的路程为L+X+nR，slow所走的路程为L+X

        又因为慢指针走一步，快指针走两步，有以下公式：

2*慢指针的路程 = 快指针的路程

        代入快慢指针路程可以得到：

     L = (n-1)R+(R-X)，n = 1，2，3...           

        当n等于1时，即相遇时，快指针刚好绕环一圈，则L = R-X 

故相遇点到入环起始结点的距离 = 链表头结点到入环起始结点的距离

 代码实现：

    ListNode* slow = head;ListNode* fast = head;ListNode* meet = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){meet = slow;break;}}

        定义快慢指针，找到相遇结点meet，找到后跳出循环。

    ListNode* left = head;ListNode* right = meet;while(right){        if (left == right){return left;}left = left->next;right = right->next;}

        找到相遇点后，让头结点和相遇点同时往后遍历，找到入环的起始结点，若相遇点为空，直接返回NULL。

完整代码：

 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* slow = head;ListNode* fast = head;ListNode* meet = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){meet = slow;break;}}ListNode* left = head;ListNode* right = meet;while(right){        if (left == right){return left;}left = left->next;right = right->next;}return NULL;
}