Home » Interview Questions » LinkedList Interview Questions » Merge a linked list into another at alternate positions

Merge a linked list into another at alternate positions


()

Given two linked lists A and B, we need to insert nodes of B into A at alternative positions of list A.

Example

Time complexity : O(n),

n is number of nodes in first list.

Algorithm

a. Traverse in the ListA until there are available positions in it.
b. Loop in ListB and insert the nodes of ListB to ListA
c. Do insertion by changing pointers.
d. Store Next pointers of Both A and B.
e. Make B as next of pointer A and next of pointer B is next of pointer A, By doing this we insert a node of ListB in ListA.
f. Move pointers of ListA and ListB.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};


/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    if (temp==NULL)
    {
        cout<<"Empty linked list"<<endl;
    }
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<" ->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

void Merge(struct LLNode *A, struct LLNode **B)
{
     struct LLNode *current_inA = A, *current_inB = *B;
     struct LLNode *next_inA, *next_inB;
   
     while (current_inA != NULL && current_inB != NULL)
     {
         //store next pointers of current pointers
         next_inA = current_inA->next;
         next_inB = current_inB->next;
         //adding node from B to A by changing:
         //next of node in B to next in A
         //move pointers
         current_inB->next = next_inA;  
         current_inA->next = current_inB;  
         current_inA = next_inA;
         current_inB = next_inB;
    }
    //change pointer of head of list B
    //remaining nodes
    *B = current_inB;
}
 
// Driver program to test above functions
int main()
{
     struct LLNode *ListA = NULL, *ListB = NULL;
     insertAtBeginning(&ListA, 8);
     insertAtBeginning(&ListA, 7);
     insertAtBeginning(&ListA, 6);
     
     insertAtBeginning(&ListB, 5);
     insertAtBeginning(&ListB, 4);
     insertAtBeginning(&ListB, 3);
     insertAtBeginning(&ListB, 2);
     insertAtBeginning(&ListB, 1);

     cout<<"Linked List A: ";
     display(&ListA);
 
     cout<<"Linked List B: ";
     display(&ListB);
    
     cout<<"Merging List B into List A at alternate positions in A";
     Merge(ListA,&ListB);
 
     cout<<"\nOutput Linked List A: ";
     display(&ListA);
 
     cout<<"Output Linked List B: ";
     display(&ListB);
 
     return 0;
}

READ  Merge K Sorted Linked Lists

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions