Home » Technical Interview Questions » LinkedList Interview Questions » Merge Two Sorted Linked Lists

Merge Two Sorted Linked Lists


Reading Time - 4 mins

In merge two sorted linked lists we have given head pointer of two linked lists, merge them such that a single linked list is obtained which has nodes with values in sorted order. return the head pointer of the merged linked list.

Note: merge the linked list in-place without using any extra space.

Example

Input

Merge Two Sorted Linked Lists

Output

Merge Two Sorted Linked Lists

Types of solution

  1. Recursive
  2. Iterative

Recursive

Approach for Merge Two Sorted Linked Lists

The idea is to recursively merge the two input linked list such that the sorted order in the merged linked list is maintained.

Algorithm

  1. Define the base case: if any of the linked lists is empty, simply return the other.
  2. Now compare data values of head nodes of both the linked lists (x and y):
    • if x.data < y.data => x.next = recurse{x.next,y}.
    • Else => y.next = recurse{x,y.next}.
  3. return the head of the recursively merged linked list.

Merge Two Sorted Linked Lists Merge Two Sorted Linked Lists Merge Two Sorted Linked Lists

Implementation

C++ program

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* blue print of node */
class Node
{
    public:
    int data;
    Node *next;
    
    Node(int num)
    {
        data = num;
        next = NULL;
    }
};

/* append a node at the end of the Linked List */
Node* insert(Node *head,int data)
{
    if(head == NULL)
        head = new Node(data);
    else
    {
        Node* temp = head;
        while(temp->next != NULL)
        temp = temp->next;
        
        temp->next = new Node(data);
    }
    
    return head;
}

/* print the Linked List */
void print(Node *head)
{
    if(head != NULL)
    {
        cout<<head->data<<" ";
        print(head->next);
    }
}

/* function that merges 2 Linked Lists keeping the Sorted 
Order & returns the head of of the merged Linked List */ 
Node *sortedMerge(Node* x,Node* y)
{
    if(x == NULL)
    return y;
    
    if(y == NULL)
    return x;
    
    if(x->data < y->data)
    {
        x->next = sortedMerge(x->next,y);
        return x;
    }
    else
    {
        y->next = sortedMerge(x,y->next);
        return y;
    }
}

/* function to implement above */
int main()
{
    Node *x = NULL, *y = NULL;
    
    /* construct the first Linked List */
    x = insert(x,3);
    x = insert(x,4);
    x = insert(x,7);
    x = insert(x,9);
    cout<<"First Linked List : ";
    print(x);
    
    cout<<endl;
    
    /* construct the second Linked List */
    y = insert(y,1);
    y = insert(y,2);
    y = insert(y,5);
    y = insert(y,6);
    y = insert(y,8);
    cout<<"Second Linked List : ";
    print(y);
    
    cout<<endl;
    
    /* merge the 2 Linked Lists and print */
    cout<<"Merged Linked List in Sorted Order : ";
    Node *result = sortedMerge(x,y);
    print(result);
    
    return 0;
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Java Program

import java.util.*;
import java.io.*;

class TutorialCup
{
    /* blue print of node */
    static class Node
    {
        int data;
        Node next;
        
        Node(int num)
        {
            data = num;
            next = null;
        }
    };
    
    /* append a node at the end of the Linked List */
    static Node insert(Node head,int data)
    {
        if(head == null)
            head = new Node(data);
        else
        {
            Node temp = head;
            while(temp.next != null)
            temp = temp.next;
            
            temp.next = new Node(data);
        }
        
        return head;
    }
    
    /* print the Linked List */
    static void print(Node head)
    {
        if(head != null)
        {
            System.out.print(head.data + " ");
            print(head.next);
        }
    }
    
    /* function that merges 2 Linked Lists keeping the Sorted 
    Order & returns the head of of the merged Linked List */ 
    static Node sortedMerge(Node x,Node y)
    {
        if(x == null)
        return y;
        
        if(y == null)
        return x;
        
        if(x.data < y.data)
        {
            x.next = sortedMerge(x.next,y);
            return x;
        }
        else
        {
            y.next = sortedMerge(x,y.next);
            return y;
        }
    }
    
    /* function to implement above */
    public static void main (String[] args)
    {
        Node x = null, y = null;
        
        /* construct the first Linked List */
        x = insert(x,3);
        x = insert(x,4);
        x = insert(x,7);
        x = insert(x,9);
        System.out.print("First Linked List : ");
        print(x);
        
        System.out.println();
        
        /* construct the second Linked List */
        y = insert(y,1);
        y = insert(y,2);
        y = insert(y,5);
        y = insert(y,6);
        y = insert(y,8);
        System.out.print("Second Linked List : ");
        print(y);
        
        System.out.println();
        
        /* merge the 2 Linked Lists and print */
        System.out.print("Merged Linked List in Sorted Order : ");
        Node result = sortedMerge(x,y);
        print(result);
    }
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Complexity Analysis

  1. Time Complexity: T(n) = O(a+b).
  2. Space Complexity: A(n) = O(1)
READ  Add two numbers

a = size of the first linked list.

b = size of the second linked list.

Iterative

Approach for Merge Two Sorted Linked Lists

The idea is to convert recursive code into an iterative one.

Algorithm

  1. creates two node pointers head and tail.
  2. assign head.next = new Node(-1), allocating dummy node to head so that it becomes easy to merge both the linked list. the head pointer is used to retain the head of the merged linked list.
  3. the tail is used to store the end of the merged linked list, the tail pointer is used append nodes from x and y at the end of the merged list.
  4. Traverse both the input lists x and y simultaneously until reaching the end of one of them.
  5. For each node of x and y consider:
    1. if x.data < y.data => tail.next = x and move to next node in list x.
    2. Else tail.next = y and move to the next node in list y.
  6. If during traversal any of the list x or y becomes empty, simply append the nonempty list to the merged list.
  7. In the end return head.next.

Merge Two Sorted Linked Lists Merge Two Sorted Linked Lists

Implementation

C++ program

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* blue print of node */
class Node
{
    public:
    int data;
    Node *next;
    
    Node(int num)
    {
        data = num;
        next = NULL;
    }
};

/* append a node at the end of the Linked List */
Node* insert(Node *head,int data)
{
    if(head == NULL)
        head = new Node(data);
    else
    {
        Node* temp = head;
        while(temp->next != NULL)
        temp = temp->next;
        
        temp->next = new Node(data);
    }
    
    return head;
}

/* print the Linked List */
void print(Node *head)
{
    if(head != NULL)
    {
        cout<<head->data<<" ";
        print(head->next);
    }
}

/* function that merges 2 Linked Lists keeping the Sorted 
Order & returns the head of of the merged Linked List */
Node* utility(Node* x,Node* y) 
{ 
    /* head is used to return head of the merged linked list */
    Node *head = new Node(-1);
    /* tail is used to append a node at end 
    of the merged linked list at each step */
    Node *tail = head;
    
    /* process until one of the linked list becomes empty */
    while(x && y)
    {
        if(x->data < y->data)
        {
            tail->next = x;
            x = x->next;
        }
        else
        {
            tail->next = y;
            y = y->next;
        }
        
        tail = tail->next;
    }
    
    /* if any of the linked list gets exhausted 
    append the other one to the merged list */
    if(x == NULL)
    tail->next = y;
    
    if(y == NULL)
    tail->next = x;
    
    return head->next;
} 

/* function to merge two sorted linked 
lists using a utility function */
Node *sortedMerge(Node* x,Node* y)
{
    if (x == NULL) 
        return y; 
    if (y == NULL) 
        return x; 
  
    /* start with the linked list whose head data is the lesser */
    if (x->data < y->data) 
        return utility(x,y); 
    else
        return utility(y,x); 
}

/* function to implement above */
int main()
{
    Node *x = NULL, *y = NULL;
    
    /* construct the first Linked List */
    x = insert(x,3);
    x = insert(x,4);
    x = insert(x,7);
    x = insert(x,9);
    cout<<"First Linked List : ";
    print(x);
    
    cout<<endl;
    
    /* construct the second Linked List */
    y = insert(y,1);
    y = insert(y,2);
    y = insert(y,5);
    y = insert(y,6);
    y = insert(y,8);
    cout<<"Second Linked List : ";
    print(y);
    
    cout<<endl;
    
    /* merge the 2 Linked Lists and print */
    cout<<"Merged Linked List in Sorted Order : ";
    Node *result = sortedMerge(x,y);
    print(result);
    
    return 0;
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Java Program

import java.util.*;
import java.io.*;

class TutorialCup
{
    /* blue print of node */
    static class Node
    {
        int data;
        Node next;
        
        Node(int num)
        {
            data = num;
            next = null;
        }
    };
    
    /* append a node at the end of the Linked List */
    static Node insert(Node head,int data)
    {
        if(head == null)
            head = new Node(data);
        else
        {
            Node temp = head;
            while(temp.next != null)
            temp = temp.next;
            
            temp.next = new Node(data);
        }
        
        return head;
    }
    
    /* print the Linked List */
    static void print(Node head)
    {
        if(head != null)
        {
            System.out.print(head.data + " ");
            print(head.next);
        }
    }
    
    /* function that merges 2 Linked Lists keeping the Sorted 
    Order & returns the head of of the merged Linked List */
    static Node utility(Node x,Node y) 
    { 
        /* head is used to return head of the merged linked list */
        Node head = new Node(-1);
        /* tail is used to append a node at end 
        of the merged linked list at each step */
        Node tail = head;
        
        /* process until one of the linked list becomes empty */
        while(x != null && y != null)
        {
            if(x.data < y.data)
            {
                tail.next = x;
                x = x.next;
            }
            else
            {
                tail.next = y;
                y = y.next;
            }
            
            tail = tail.next;
        }
        
        /* if any of the linked list gets exhausted 
        append the other one to the merged list */
        if(x == null)
        tail.next = y;
        
        if(y == null)
        tail.next = x;
        
        return head.next;
    } 

    /* function to merge two sorted linked 
    lists using a utility function */
    static Node sortedMerge(Node x,Node y)
    {
        if (x == null) 
            return y; 
        if (y == null) 
            return x; 
      
        /* start with the linked list whose head data is the lesser */
        if (x.data < y.data) 
            return utility(x,y); 
        else
            return utility(y,x); 
    }

    
    /* function to implement above */
    public static void main (String[] args)
    {
        Node x = null, y = null;
        
        /* construct the first Linked List */
        x = insert(x,3);
        x = insert(x,4);
        x = insert(x,7);
        x = insert(x,9);
        System.out.print("First Linked List : ");
        print(x);
        
        System.out.println();
        
        /* construct the second Linked List */
        y = insert(y,1);
        y = insert(y,2);
        y = insert(y,5);
        y = insert(y,6);
        y = insert(y,8);
        System.out.print("Second Linked List : ");
        print(y);
        
        System.out.println();
        
        /* merge the 2 Linked Lists and print */
        System.out.print("Merged Linked List in Sorted Order : ");
        Node result = sortedMerge(x,y);
        print(result);
    }
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Complexity Analysis

  1. Time Complexity: T(n) = O(a+b).
  2. Space Complexity: A(n) = O(1), head and tail pointers are used which take constant memory.
READ  Insert Node in the Sorted Linked List

a = size of the first linked list.

b = size of the second linked list.

References

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