Linked List Cycle II

题目描述

环形链表 II：

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

示例：

输入：head = [3, 2, 0, -4], pos = 1, pos表示入环点
输出：tail connects to node index 1

输入：head = [1, 2], pos = 0
输出：tail connects to node index 0

输入：head = [1], pos = -1
输出：no cycle

解法

方法一：哈希表法

遍历节点，同时，在哈希表检查是否存在相同指针，如果存在则返回。 如果不存在，将当前节点存入哈希表。 直到节点遍历完，或者找到入环点。

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func detectCycle(head *ListNode) *ListNode {
    nodeM := make(map[*ListNode]int)

    for head != nil {
        if _, ok := nodeM[head]; ok {
            return head
        }
        nodeM[head] = 1

        head = head.Next
    }

    return nil
}

方法二：快慢指针

快指针走两步，慢指针走一步，如果未找到相遇点，则不成环。 如果找到相遇点，此时相遇点一定在环内，保存相遇点。 使用两个指针，分别指向相遇点和链表头，每次都只走一步，直到相遇，即可找到入环点。

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        // 如果找到相遇点
        if slow == fast {
            // 一个指针指向链表头
            // 一个指针指向相遇点
            // 每次走一步 直到相遇
            fast = head
            for slow != fast {
                slow = slow.Next
                fast = fast.Next
            }
            return slow
        }
    }
    return nil
}