Skip to content
CodeItRaw
Linked Lists

Lesson 3/4

The two pointers can also have the same speed and different starts. To find the k-th node from the end, send one of them k steps ahead first, then walk both together. When the one in front reaches the end, the one behind is exactly k steps back, on the node you want.

lead = head
for _ in range(k):
    lead = lead.next
trail = head
while lead is not None:
    lead = lead.next
    trail = trail.next
return trail
The gap between them never changes; what changes is only how far the two have moved together. No separate pass is needed to measure the length.

With different speeds you learn something else: does the chain have a cycle? If it has none the fast pointer reaches the end and it is over. If it has one, the fast pointer goes round and round inside and catches the slow one up from behind: the two meet on the same node. There is no need to keep the nodes seen in a set.

Tasks

Tasks open in order. Solve them all and the next lesson opens.

This lesson's tasks open when the lessons before it are finished. You can read the explanation now.

  1. 01

    k-th From the End

    Function

  2. 02

    Endless Loop

    Function

If you would rather not wait for the order, every problem is open without locks: Problem list