Fast & Slow Pointers

Posted on

掌握判环以及判环的变形。while 循环的条件往往是 r and r.next 存在，过程中可以顺便获取 middle pointer。

The Fast & Slow Pointers approach is a pointer algorithm that uses two pointers which move through the array (or linked list) at different speeds. This approach is quite useful when dealing with cyclic linked lists or arrays.

By moving at different speeds (say, in a cyclic linked list), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
l = r = head
while r and r.next:
    l = l.next
    r = r.next.next
    if l == r:
        break
else:
    return

l = head
while l != r:
    l = l.next
    r = r.next

return l

LeetCode

141. Linked List Cycle
142. Linked List Cycle II
202. Happy Number
876. Middle of the Linked List
234. Palindrome Linked List
143. Reorder List
457. Circular Array Loop