142.M 环形链表 II

Problem: 142. 环形链表 II

思路

首先让fast和slow两个指针分别指向头结点，fast每次走两步，slow每次走一步。两者第一次相遇后，让一个新的指针p指向头结点，然后与slow一起同步向后运动，它们相遇之处即为入环的第一个节点。

Code

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	slow, fast := head, head
	for fast != nil {
		if fast.Next == nil {
			return nil
		}

		slow = slow.Next
		fast = fast.Next.Next

		if slow == fast {
			// 第一次相遇
			// 让p指向头结点，与慢指针一起往后走，直到相遇
			p := head
			for p != slow {
				p = p.Next
				slow = slow.Next
			}

			return p
		}
	}

	return nil
}