Runner technique to combine two equal Linked Lists

Question

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?

Answer 1

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.

Answer 2

Start p2 at second position.

a1(p1)-> a2 (p2) -> a3 -> a4 -> b1 -> b2 -> b3 -> b4  
a1-> a2 (p1) -> a3 -> a4 (p2)-> b1 -> b2 -> b3 -> b4  
a1-> a2  -> a3(p1) -> a4 -> b1 -> b2(p2) -> b3 -> b4  
a1-> a2  -> a3 -> a4(p1) -> b1 -> b2 -> b3 -> b4(p2)  

Answer 3

You can simply implement by using Java:

public static void findMidElOfLinkedList(FindMidElementOfLinkedList findMidElementOfLinkedList) {
    Node node = findMidElementOfLinkedList.head;
    Node slow = node;
    Node fast = node;

    while (fast != null && fast.next != null) {
        fast = fast.next.next; // increase 2
        slow = slow.next; // increate 1
    }
    System.out.println(slow.data);
    /*
    * Slow runner goes at a pace of 1 element per move, fast runner goes 2 elements per move.
    When the fast runner reaches the end of the linked list, then slow runner is sitting at the middle. Testing this out for one/two middle cases work.
    Time O(N), faster than the previous brute force method, Space: O(1).
    * */
}