Two Pointers
Loading
Loading
Two Pointers
Different speeds turn distance questions into termination questions.
By the end of this chapter
Move one pointer one step and the other two. Their relative speed is one step per iteration. Once both are inside a cycle, the distance between them shrinks by one each time, so it must reach zero.
def has_cycle(head): slow = fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow is fast: # identity, not value return True return FalseA singly linked list cannot be walked backwards, which makes "the k-th node from the end" awkward. Starting one pointer k steps ahead converts it into a forward question.
1 → 2 → 3 → 4 → 5, remove the 2nd from the endlead 3 steps aheadgap of k + 1 so trail lands before the targetadvance bothuntil lead falls off the endtrail at 3unlink trail.next1 → 2 → 3 → 5Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 3 practice problems.