环形链表2

1. 题目描述

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

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

2. 思路

1. 思路一
   • 使用set记录走过的节点
   • 如果下一个节点在set中，说明是环节点，返回之
2. 思路二
   • 
   • 
   • 快慢指针
   • 快指针走两步，慢指针走一步
   • 注意两指针虽然相遇，但是相遇的节点却可能不是环的入口节点

3. 实现

3.1. map

func detectCycle(head *ListNode) *ListNode {
	count := make(map[*ListNode]bool, 0)
	current := head
	for current != nil {
		if count[current] {
			return current
		}
		count[current] = true
		current = current.Next
	}

	return nil
}

3.2. 快慢指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    hasCycle := false
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            hasCycle = true
            break
        }
    }

    if !hasCycle {
        return nil
    }

    fast = head
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

4. 参考

• 环形链表 II（双指针法，清晰图解） - 环形链表 II - 力扣（LeetCode）
• 环形链表 II - 环形链表 II - 力扣（LeetCode）