# Runner technique to combine two equal Linked Lists

So, I am facing a doubt here.

I was reading the book Cracking the coding Interview. The following text is written over there.

Suppose you had a linked list `a1->a2....->an->b1->b2....bn`, and you want to rearrange it into `a1->b1->a2->b2->.....an->bn`. You don't know the length of the linked list but all you know is that it is an even number.

(Here both the linked lists are of same length)

You could have one pointer p1 (fast pointer) move every two elements for every one move that p2 makes. When p1 hits the end of the linked list, p2 will be at the endpoint. Then, move p1 back to the front and begin "weaving" the elements. On each iteration, p2 selects an element and inserts it after p1.

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 (length = 6). 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.
``````

Am I going somewhere wrong?

#### Best Solution

Let `n = 2`. We are starting with a list:

``````a1 -> a2 -> b1 -> b2
``````

Let `p1` be a "fast" pointer initially pointing to the successor of head.
Let `p2` be a "slow" pointer initially pointing to the head.

``````      p1
a1 -> a2 -> b1 -> b2
p2
``````

We move `p1` by two and `p2` by one until `p1` reaches the end of the list (there is no next).

``````                  p1
a1 -> a2 -> b1 -> b2
p2
``````

Move `p1` back to the head.

``````p1
a1 -> a2 -> b1 -> b2
p2
``````

Advance `p2`.

``````p1
a1 -> a2 -> b1 -> b2
p2
``````

"Weaving" starts.

Take element pointed by `p2` and move it after `p1`. Advance `p1` after inserted element.

``````            p1
a1 -> b1 -> a2 -> b2
p2
``````

Take element pointed by `p2` and move it after `p1`. Advance `p1` after inserted element.

``````                       p1
a1 -> b1 -> a2 -> b2
p2
``````

`p1` is null, terminate.