跳转至

LC142 - 环形链表II

LinkedListCycle.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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 {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }
    fast = head
    for {
        if slow == fast {
            return slow
        }
        slow = slow.Next
        fast = fast.Next
    }
}

快慢指针。若链表有环，则快慢指针必然会在环上重新相遇，此时将快指针重新归位至头节点，快慢指针每次走一步，相遇位置即为入环节点。