【链表】leetcode142——环形链表（双指针法）

编号142：环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

思路

这里主要解决两个问题：

1. 判断当前链表是否有环？
2. 计算出链表的环入口处

现在咱们一个一个解决，如何判断链表中是否有环呢，这是一个经典的问题。通常通过设置快慢指针，即双指针法来进行判断，快指针fast从链表的头节点出发，每次移动两个单位，慢指针slow也从链表的头节点出发，每次移动一个单位，如过两个指针在同一位置（相遇的位置一定在环内）遇到说明该链表存在环（因为fast指针与slow指针相差一个单位，一步一步的在"追赶"slow指针）。

下面如何计算出链表的环入口呢，引入一张图予以说明：

这里假设链表头节点到环入口处距离为x个单位，环入口处到快慢指针相遇的位置距离y单位，快慢指针相遇的位置到环入口处距离z个单位。slow指针到相遇位置走过的距离为x+y，fast指针到相遇位置走过的距离为x+y+n(y+z)（n表示fast指针所走过的圈数），由于fast指针是每次走两个单位，slow指针每次走一个单位，故fast指针走过的距离是slow指针走过距离的两倍。具体如下：

由上述公式可知，当n=1时，fast指针走过一圈x=z。即快慢指针相遇的地方引入新的指针，一个index1指向头节点，一个index2指向快慢指针相遇的节点，然后这个两个新的指针同时开始以一个单位进行移动，相遇时即为环入口处位置。

具体代码如下：

//Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

/*环形链表II 主要考虑两个问题：
1.判断链表是否有环？
A:利用双指针(快慢指针，fast指针两步一单位，slow指针一步一单位，如果两者相遇  说明存在环)
2.如果有环如何找到这个环的入口？
A:在两个指针相遇的位置设置一个指针index1,再在头节点设置一个指针index2,两者相遇的位置就是环入口处
*/
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast !=nil && fast.Next !=nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow{ //快慢指针相遇位置
            index1 := head
            index2 := slow
            for index1 != index2{
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }
    return nil //没有环
}

【链表】leetcode142——环形链表（双指针法）

原文：https://www.cnblogs.com/zmk-c/p/14393976.html