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.