How can the runner technique be used to arrange this linked list?

[ainster31]

Homework Statement

Homework Equations

The Attempt at a Solution

I don't understand how when p1 hits the end of the linked list, p2 will be at the midpoint.

This is how I am imagining it if n=3. Each step below represents an iteration.

1. a1 (p1, p2)->a2->a3->b1->b2->b3

2. a1->a2 (p2)->a3 (p1)->b1->b2->b3

3. a1->a2->a3 (p2)->b1->b2 (p1)->b3

4. Index out of bounds error because p2 now points to a node after b3.

 

[jedishrfu]

It says you don't know the list length but you do know that its length is even.

Hence you can't have n=3 in your thought experiment.

So if n=10 then:

i=0 p1=0 p2=2
i=1 p1=1 p2=4
i=2 p1=2 p2=6
i=3 p1=3 p2=8
i=4 p1=4 p2=0 // p2 is reset to the beginning of the list and p1 is at the midpoint

 

[ainster31]

Oh, so I guess they wanted n to be even. Even if n is odd, the linked list length is even since the length of the linkedlist is 2n.

 

[jedishrfu]

Oh, so I guess they wanted n to be even. Even if n is odd, the linked list length is even since the length of the linkedlist is 2n.

Only the linked list length is even, if n is half the list length then n can be even or odd.

 

[rezeew]

The runner technique can be used to arrange a linked list by using two pointers, p1 and p2, where p1 moves at a slower pace than p2. This approach can be used to find the midpoint of the linked list by having p1 move one node at a time and p2 move two nodes at a time. When p2 reaches the end of the linked list, p1 will be at the midpoint. This can be useful for sorting the linked list by splitting it into two smaller lists at the midpoint, sorting each list separately, and then merging them back together in sorted order. Alternatively, the runner technique can also be used to check for cycles in the linked list by having p1 and p2 move at different speeds and checking if they ever meet again.