Merge alternate nodes of the two lists

We have already seen the code to merge two sorted linked list, such that the final list is also sorted. The logic and code can be found in this post.

In this post, we want to merge the two lists in a way that in the final list, element comes from the two lists alternately as shown below.

The red elements in the final list are from the second input list and the black ones are from the first input list.

Solution:  Let us write the code in Java this time. the structure of Node in Java is:

class Node{
    public int data;
    public Node next;
}

we have not written the getter/setter methods in this class. We are keeping it simple by making the properties public. The signature of the function that merge the two lists is should be

public void mergeAlternate(Node h1, Node h2)

After the two lists are merged, h1 will point to the head of the merged list (final list) and h2 will be pointing to the second list (this pointer will be irrelevant). The logic of merge is simple, we set the next pointers of first node from each list in one iteration of the loop and move each of the two pointers forward. If the two pointers are initially pointing like below:

Then after the first iteration of the loop, the next pointers of nodes poinnted to by h1 and h2 are set, and both of them move forward to point to the next nodes in their respective linked lists.

We should keep doing it as long as there are nodes in both the lists. When one of the two (or both) lists becomes empty, then we should stop and just return. Below is the code for this logic:

// MERGE THE TWO LISTS POINTED TO BY h1 AND h2 and return the head of merged list.
// IT DOES NOT MERGE IN A SORTED ORDER, BUT, PUT
// NODES FROM ALTERNATE LISTS IN THE FINAL LIST
// h1 WILL BE THE HEAD OF FINAL LIST
public Node alternateMerge(Node h1, Node h2)
{
    // BOUNDARY CONDITIONS
    if(h1 == null){ return h2; }
    if(h2 == null){ return h1; }
    Node head = h1;
    while(h1 != null && h2 != null)
    {
        Node temp = h1.next;
        h1.next = h2;
        h1 = temp;
        // IF FIRST LIST IS NULL. KEEP 2nd AS IT IS
        if(h1 == null){ break; }
        temp = h2.next;
        h2.next = h1;
        h2 = temp;
    }
    return head;
}

Note that, if any of the two list becomes empty, then we move out of the loop leaving the trailing nodes of the other list at the end. This code takes O(n) time and constant extra memory. Below is a running Java program for the same:

public class RTDemo {
    class Node{
        public int data;
        public Node next;
        public Node(int x){
            data = x; next =null;
        }
    }
    // CREATING A SAMPLE LIST
    public Node createList(){
        Node h = new Node(1);
        h.next = new Node(2);
        h.next.next = new Node(3);
        h.next.next.next = new Node(4);
        h.next.next.next.next = new Node(5);
        h.next.next.next.next.next = new Node(6);
        h.next.next.next.next.next.next = new Node(7);
        h.next.next.next.next.next.next.next = new Node(8);
        return h;
    }
    // HELPER FUNCTION: PRINT THE LIST
    public void printlist(Node h)
    {
        System.out.println();
        for(Node temp = h; temp != null; temp = temp.next)
            System.out.print(temp.data+" ");
    }
    public Node alternateMerge(Node h1, Node h2)
    {
        // BOUNDARY CONDITIONS
        if(h1 == null){ return h2; }
        if(h2 == null){ return h1; }
        Node head = h1;
        while(h1 != null && h2 != null)
        {
            Node temp = h1.next;
            h1.next = h2;
            h1 = temp;
            // IF FIRST LIST IS NULL. KEEP 2nd AS IT IS
            if(h1 == null){ break; }
            temp = h2.next;
            h2.next = h1;
            h2 = temp;
        }
        return head;
    }
    public static void main(String[] args)
    {
        RTDemo obj = new RTDemo();
        Node h1 = obj.createList();
        Node h2 = obj.createList();
        obj.printlist(h1);
        obj.printlist(h2);
        Node mh = obj.alternateMerge(h1, h2);
        obj.printlist(mh);
    }
}