Runner technique to combine two equal Linked Lists

algorithmlinked-list

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.

Related Question