Merge a Linked List into another Linked List at alternate positions

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given two linked lists, A and B. We should merge the second list into the first one at alternate positions. The second linked list should become empty.

Problem Statement Understanding

Let's try to understand this problem with help of examples.

Suppose the given linked lists are:

We have add the elements of the second list to the first list, at alternate positions.

• First, we will add the first element of B after the first element of A -
  
  

• Now, add the second element of B after the second element of old A -
  
  

• Now, add the third element of B after the third element of old A
  
  

• Now, add the fourth element of B after the fourth element of old A

B: Empty list

After adding the elements of the second list to the first list at alternate positions, the final list will be:

Input:

Output:

Explanation: The nodes of the second linked list are merged with the first linked list at alternate positions.

I think from the above example the problem statement is clear, so we should now think how we can approach this problem. Try to come up with a approach, it may be bruteforce but before jumping to approach section try to think how will you approach it.

Note: We should keep in mind that we cannot create a new linked list. We have to alter the first list.

Approach

The main idea is to iterate using a loop while there are available positions in the first list and insert nodes of the linked list by changing pointers. We should also note that the head of the first link will never change, but the head of the second list may change, so we have to use one pointer for the first list and two pointers for the second list. We can get a better idea by looking at the algorithm.

Algorithm

• Traverse in FirstList until there are available positions in it.
• Loop in SecondList and insert nodes of SecondList to FirstList.
• Do insertion by changing pointers.
• Store next pointers of both A and B in nextA and nextB and current pointers of both A and B in currA and currB.
• Make B as the next of pointer A and next of pointer B is next of pointer A. By doing this we insert a node of SecondList in FirstList:
  currB - > next = nextA
  currA - > next = currB
  currA=nextA
  currB=nextB
• Move pointers of FirstList and SecondList and again perform the above steps of insertion of list B nodes in list A at alternate position.

Dry Run

Code Implementation

#include 
using namespace std;
struct LLNode
{
    int data;
    struct LLNode* next;
};

void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; 
        
    else
        {
            curr->next=*head;
            *head=curr;
        }
        
       
}

void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    if (temp==NULL)
    {
        cout<<"Empty linked list"<next!=NULL)
            cout<data<<" ->";
            else
            cout<data;
            
            temp=temp->next;
        }
    cout<next;
         nextB = currB->next;
         currB->next = nextA;  
         currA->next = currB;  
         currA = nextA;
         currB = nextB;
    }
    *B = currB;
}

int main()
{
     struct LLNode *FirstList = NULL, *SecondList = NULL;
     insertAtBeginning(&FirstList, 18);
     insertAtBeginning(&FirstList, 17);
     insertAtBeginning(&FirstList, 7);
     insertAtBeginning(&FirstList, 8);
     
     insertAtBeginning(&SecondList, 4);
     insertAtBeginning(&SecondList, 2);
     insertAtBeginning(&SecondList, 10);
     insertAtBeginning(&SecondList, 32);
     cout<<"Linked List A: ";
     display(&FirstList);
 
     cout<<"Linked List B: ";
     display(&SecondList);
    
     cout<<"Merging List B into List A at alternate positions in A";
     Merge(FirstList,&SecondList);
 
     cout<<"\nOutput Linked List A: ";
     display(&FirstList);
 
     cout<<"Output Linked List B: ";
     display(&SecondList);
 
     return 0;
}

public class LinkedList
{
    Node head; 
 

    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }

    void push(int new_data)
    {

        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;
    }

    void merge(LinkedList q)
    {
        Node p_curr = head, q_curr = q.head;
        Node p_next, q_next;

        while (p_curr != null && q_curr != null) {

            p_next = p_curr.next;
            q_next = q_curr.next;

            q_curr.next = p_next; 
            p_curr.next = q_curr; 

            p_curr = p_next;
            q_curr = q_next;
        }
        q.head = q_curr;
    }

    void printList()
    {
        Node temp = head;
        while (temp != null)
        {
           System.out.print(temp.data+" ");
           temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        LinkedList llist1 = new LinkedList();
        LinkedList llist2 = new LinkedList();
        llist1.push(18);
        llist1.push(17);
        llist1.push(7);
        llist1.push(8);
 
        System.out.println("Linked List A: ");
        llist1.printList();
 
        llist2.push(4);
        llist2.push(2);
        llist2.push(10);
        llist2.push(32);
 
        System.out.println("Linked List B: ");

        System.out.println("Merging List B into List A at alternate positions in A");
 
        llist1.merge(llist2);
 
        System.out.println("Output Linked List A: ");
        llist1.printList();
 
        System.out.println("Output Linked List B: ");
        llist2.printList();
    }
}

Output

Linked List A: 5 ->7 ->17 ->13
Linked List B: 12 ->10 ->2 ->4
Merging List B into List A at alternate positions in A
Output Linked List A: 5 ->12 ->7 ->10 ->17 ->2 ->13 ->4
Output Linked List B: Empty linked list

So, in this article, we have tried to explain the most efficient approach to merge a linked list into another linked list at alternate positions. This approach requires no extra space, and that is what makes this question an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.