环形链表

环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

https://leetcode-cn.com/problems/linked-list-cycle-ii/

检测是否存在环形链表

快慢指针

1
2
3
4
5
6
7
8
9
10
11
func hasCycle(head *ListNode) bool {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}

环形链表的起点

快慢指针相遇后，将其中一个指回开头，以同样的速度前进，再次相遇的地方就是环的起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            // 开始寻找环起点
            fast = head 
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return fast
        }
    }
    return nil
}