Abhinav Kaushik

Data Structures and Algorithms

Merge Two Sorted Linked Lists

Problem Statement

Given two linked lists which are sorted in increasing order. Merge both lists into a single linked list which is also sorted in increasing order.

Example

Input :

List1: 1->2->4->6->9
List2: 3->4->7->8

Output:

New List: 1->2->3->4->4->6->7->8->9

Explanation

As we can see that if we merge both lists and arrange them in increasing order, it will become 1->2->3->4->4->6->7->8->9.

Constraints

$1 <= |List1| <= 10^6$ (1 <= Size of the first linked list <= $10^6$)

$1 <= |List2| <= 10^6$ (1 <= Size of the second linked list <= $10^6$)

$1 <= \text{Node.data} <= 10^6$ (1 <= Value of the Nodes <= $10^6$)

Approach 1 (Using Recursion)

In this approach, we will use Recursion to merge two sorted linked lists. This is one of the easiest approaches to solving this problem. The main intuition behind the approach is that we can keep the track of current nodes in both lists through the recursive function by passing the current nodes as a parameter. The node with the lesser node value will be updated in the recursive call each time. This will lead to the merging of two lists.

Algorithm

  • Create a new Node named result
  • Check if the head1 is empty, and return head2
  • Check if head2 is empty, return head1
  • Now find the node which has the smaller value (head1 or head2)
  • Update the result with that node and call the recursive function accordingly
  • Finally, return the result

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node* next; 
};
Node* MergeSortedLists(Node* head1, Node* head2) 
{ 
    Node* result = NULL; 

    if (head1 == NULL) 
        return(head2); 
    else if (head2 == NULL) 
        return(head1); 

    if (head1->data <= head2->data) 
    { 
        result = head1; 
        result->next = MergeSortedLists(head1->next, head2); 
    } 
    else
    { 
        result = head2; 
        result->next = MergeSortedLists(head1, head2->next); 
    } 
    return(result); 
} 
void insert(Node** head_ref, int new_data) { 
    Node* newNode = new Node();
    newNode->data = new_data; 
    newNode->next = (*head_ref); 
    (*head_ref) = newNode; 
} 
void printNodes(Node *node) { 
    while (node!=NULL) { 
        cout<<node->data<<" "; 
        node = node->next; 
    } 
}

int main() 
{ 
    Node* result = NULL; 
    Node* head1 = NULL; 
    Node* head2 = NULL; 

    insert(&head1, 9);
    insert(&head1, 6);
    insert(&head1, 4); 
    insert(&head1, 2); 
    insert(&head1, 1); 

    insert(&head2, 8);
    insert(&head2, 7); 
    insert(&head2, 4); 
    insert(&head2, 3); 
    result = MergeSortedLists(head1, head2); 

    printNodes(result); 
    return 0; 
}

Output

1 2 3 4 4 6 7 8 9

Java Implementation

import java.util.*;
class Node
{
    int data;
    Node next;
    Node(int d) {data = d;
                next = null;}
}

class Main
{
    Node head;
    public void addToTheLast(Node node)
    {
        if (head == null)
        {
            head = node;
        }
        else
        {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = node;
        }
    }
    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[])
    {
        Main head1 = new Main();
        Main head2 = new Main();

        head1.addToTheLast(new Node(1));
        head1.addToTheLast(new Node(2));
        head1.addToTheLast(new Node(4));
        head1.addToTheLast(new Node(6));
        head1.addToTheLast(new Node(9));

        head2.addToTheLast(new Node(3));
        head2.addToTheLast(new Node(4));
        head2.addToTheLast(new Node(7));
        head2.addToTheLast(new Node(8));


        head1.head = new Mergesortedlists().MergeSortedLists(head1.head, head2.head);
        head1.printList();  

    }
}


class Mergesortedlists 
{
    public Node MergeSortedLists(Node head1, Node head2) 
    {

        if(head1 == null) return head2;
        if(head2 == null) return head1;

        if(head1.data < head2.data) 
        {
            head1.next = MergeSortedLists(head1.next, head2);
            return head1;
        }
        else 
        {
            head2.next = MergeSortedLists(head1, head2.next);
            return head2;
        }

    }
}

Output

1 2 3 4 4 6 7 8 9

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next

    def insert(self, newData):
        newNode = Node(newData)
        if self.head is None:
            self.head = newNode
            return

        last = self.head
        while last.next:
            last = last.next

        last.next = newNode

def mergeSortedLists(head1, head2):

    temp = None

    if head1 is None:
        return head2

    if head2 is None:
        return head1

    if head1.data <= head2.data:
        temp = head1
        temp.next = mergeSortedLists(head1.next, head2)

    else:
        temp = head2
        temp.next = mergeSortedLists(head1, head2.next)

    # return the temp list.
    return temp


# Create 2 lists
head1 = LinkedList()
head2 = LinkedList()

head1.insert(1)
head1.insert(2)
head1.insert(4)
head1.insert(6)
head1.insert(9)

head2.insert(3)
head2.insert(4)
head2.insert(7)
head2.insert(8)

head1.head = mergeSortedLists(head1.head, head2.head)

head1.printList()

Output

1 2 3 4 4 6 7 8 9

Complexity Analysis

Time Complexity Analysis
In this algorithm, we are using recursion to merge two sorted linked lists, and the recursion will use the time complexity equal to the sum of lengths of both the list, i.e. O(N+M) or in general we can consider it as O(N) time complexity

So the total worst-case time complexity for this approach to merge two sorted linked lists is O(N) + O(M) = O(N+M) = O(N)

Space Complexity Analysis
In this approach, we are using recursion and the recursion will take space complexity equal to the sum of lengths of both the list, i.e. O(N+M) or in general we can consider it as O(N) space complexity

Time Complexity: O(N)
Space Complexity: O(N)

Approach 2 (Using Temporary Dummy Node)

In this approach, we will use a temporary dummy node as a start of the resultant list. The main intuition behind this approach is that first we will create a dummy node and we will add the new nodes at its rear end, which will be created by comparing the current nodes of both the lists i.e. the new node will be created with a smaller node value among both lists, finally, we will return the dummy.next, which will be the final result.

Algorithm

  • Create two new Nodes named dummy and result
  • Initialize result as &dummy (initializing result with the address of the dummy node).
  • Initialize dummy.next with null
  • If any of the head1 or head2 is null, then update the result‘s next pointer with the other node and break out of the loop.
  • Now find the node which has the smaller value (head1 or head2)
  • Update the result‘s next pointer with that node and move that node one step forward.
  • Finally return the dummy’s next pointer.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node* next; 
};
void MoveNode(Node** destRef, Node** sourceRef) 
{ 
    Node* newNode = *sourceRef; 
    assert(newNode != NULL); 

    *sourceRef = newNode->next; 

    newNode->next = *destRef; 
    *destRef = newNode; 
} 
Node* MergeSortedLists(Node* head1, Node* head2) 
{ 
    Node dummy; 

    Node* result = &dummy; 

    dummy.next = NULL; 
    while (1) 
    { 
        if (head1 == NULL) 
        { 
            result->next = head2; 
            break; 
        } 
        else if (head2 == NULL) 
        { 
            result->next = head1; 
            break; 
        } 
        if (head1->data <= head2->data) 
            MoveNode(&(result->next), &head1); 
        else
            MoveNode(&(result->next), &head2); 

        result = result->next; 
    } 
    return(dummy.next);  
} 
void insert(Node** head_ref, int new_data) { 
    Node* newNode = new Node();
    newNode->data = new_data; 
    newNode->next = (*head_ref); 
    (*head_ref) = newNode; 
} 
void printNodes(Node *node) { 
    while (node!=NULL) { 
        cout<<node->data<<" "; 
        node = node->next; 
    } 
}

int main() 
{ 
    Node* result = NULL; 
    Node* head1 = NULL; 
    Node* head2 = NULL; 

    insert(&head1, 9);
    insert(&head1, 6);
    insert(&head1, 4); 
    insert(&head1, 2); 
    insert(&head1, 1); 

    insert(&head2, 8);
    insert(&head2, 7); 
    insert(&head2, 4); 
    insert(&head2, 3); 
    result = MergeSortedLists(head1, head2); 

    printNodes(result); 
    return 0; 
}

Output

1 2 3 4 4 6 7 8 9

Java Implementation

import java.util.*;
class Node
{
    int data;
    Node next;
    Node(int d) {data = d;
                next = null;}
}

class Main
{
Node head;
public void addToTheLast(Node node)
{
    if (head == null)
    {
        head = node;
    }
    else
    {
        Node temp = head;
        while (temp.next != null)
            temp = temp.next;
        temp.next = node;
    }
}
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[])
{
    Main head1 = new Main();
    Main head2 = new Main();

    head1.addToTheLast(new Node(1));
    head1.addToTheLast(new Node(2));
    head1.addToTheLast(new Node(4));
    head1.addToTheLast(new Node(6));
    head1.addToTheLast(new Node(9));

    head2.addToTheLast(new Node(3));
    head2.addToTheLast(new Node(4));
    head2.addToTheLast(new Node(7));
    head2.addToTheLast(new Node(8));


    head1.head = new Mergesortedlists().MergeSortedLists(head1.head,head2.head);
    head1.printList();  

}
}


class Mergesortedlists 
{
    public Node MergeSortedLists(Node head1, Node head2) 
    {

        Node dummyNode = new Node(0);

    Node result = dummyNode;
    while(true) 
    {
        if(head1 == null)
        {
            result.next = head2;
            break;
        }
        if(head2 == null)
        {
            result.next = head1;
            break;
        }

        if(head1.data <= head2.data)
        {
            result.next = head1;
            head1 = head1.next;
        } 
        else
        {
            result.next = head2;
            head2 = head2.next;
        }

        result = result.next;
    }
    return dummyNode.next;

    }
}

Output

1 2 3 4 4 6 7 8 9

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next

    def insert(self, newData):
        newNode = Node(newData)
        if self.head is None:
            self.head = newNode
            return

        last = self.head
        while last.next:
            last = last.next

        last.next = newNode

def mergeSortedLists(head1, head2):

    dummyNode = Node(0)

    result = dummyNode
    while True:
        if head1 is None:
            result.next = head2
            break
        if head2 is None:
            result.next = head1
            break

        if head1.data <= head2.data:
            result.next = head1
            head1 = head1.next
        else:
            result.next = head2
            head2 = head2.next

        result = result.next

    return dummyNode.next


# Create 2 lists
head1 = LinkedList()
head2 = LinkedList()

head1.insert(1)
head1.insert(2)
head1.insert(4)
head1.insert(6)
head1.insert(9)

head2.insert(3)
head2.insert(4)
head2.insert(7)
head2.insert(8)

head1.head = mergeSortedLists(head1.head, head2.head)

head1.printList()

Output

1 2 3 4 4 6 7 8 9

Complexity Analysis

Time Complexity Analysis
In this algorithm, we are running a loop while either of the head1 or head2 will become null which will take time complexity equal to the minimum of lengths of both the list, i.e. min(O(N+M)) or in general we can consider it as O(N) time complexity

So the total worst-case time complexity for this approach to merge two sorted linked lists is min(O(N), O(M)) = O(N)

Space Complexity Analysis
In this approach we are just using two variables i.e. Nodes to store the pointers, so we are using constant extra space and we can consider it as O(1) space complexity

Time Complexity: O(N)
Space Complexity: O(1)

Approach 3 (Using Local References)

In this approach, we will use a local reference to store the pointers by their address, so that the changes which we will make in the pointers are reflected in the original resultant node. The main intuition behind this approach is that we will create a pointer to the node which points to the last node and initialize it with the result, which is initialized with null. After every comparison, we will update this last pointer, and we will move to its next, and automatically our result will also be updated.

Algorithm

  • Create two new Nodes named lastptr and result.
  • Initialize the result as null and lastptr as &result (initializing lastptr with the address of the result node).
  • If any of the head1 or head2 is null, then update lastptr pointer with the other node and break out of the loop.
  • Now find the node which has the smaller value (head1 or head2).
  • Update the lastref pointer with that node and move that node one step forward.
  • Move the lastref pointer one step forward.
  • Finally return the result node.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node* next; 
};
void MoveNode(Node** destRef, Node** sourceRef) 
{ 
    Node* newNode = *sourceRef; 
    assert(newNode != NULL); 

    *sourceRef = newNode->next; 

    newNode->next = *destRef; 
    *destRef = newNode; 
}
Node* MergeSortedLists(Node* head1, Node* head2) 
{ 
    Node* result = NULL;

    Node** lastptr = &result;

    while (1) {
        if (head1 == NULL) {
            *lastptr = head2;
            break;
        }
        else if (head2 == NULL) {
            *lastptr = head1;
            break;
        }
        if (head1->data <= head2->data)
            MoveNode(lastptr, &head1);
        else
            MoveNode(lastptr, &head2);

        lastptr = &((*lastptr)->next);
    }
    return (result);
} 
void insert(Node** head_ref, int new_data) { 
    Node* newNode = new Node();
    newNode->data = new_data; 
    newNode->next = (*head_ref); 
    (*head_ref) = newNode; 
} 
void printNodes(Node *node) { 
    while (node!=NULL) { 
        cout<<node->data<<" "; 
        node = node->next; 
    } 
}

int main() 
{ 
    Node* result = NULL; 
    Node* head1 = NULL; 
    Node* head2 = NULL; 

    insert(&head1, 9);
    insert(&head1, 6);
    insert(&head1, 4); 
    insert(&head1, 2); 
    insert(&head1, 1); 

    insert(&head2, 8);
    insert(&head2, 7); 
    insert(&head2, 4); 
    insert(&head2, 3); 
    result = MergeSortedLists(head1, head2); 

    printNodes(result); 
    return 0; 
}

Output

1 2 3 4 4 6 7 8 9

Java Implementation

import java.util.*;
class Node
{
    int data;
    Node next;
    Node(int d) {data = d;
                next = null;}
}

class Main
{
Node head;
public void addToTheLast(Node node)
{
    if (head == null)
    {
        head = node;
    }
    else
    {
        Node temp = head;
        while (temp.next != null)
            temp = temp.next;
        temp.next = node;
    }
}
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[])
{
    Main head1 = new Main();
    Main head2 = new Main();

    head1.addToTheLast(new Node(1));
    head1.addToTheLast(new Node(2));
    head1.addToTheLast(new Node(4));
    head1.addToTheLast(new Node(6));
    head1.addToTheLast(new Node(9));

    head2.addToTheLast(new Node(3));
    head2.addToTheLast(new Node(4));
    head2.addToTheLast(new Node(7));
    head2.addToTheLast(new Node(8));


    head1.head = new Mergesortedlists().MergeSortedLists(head1.head,head2.head);
    head1.printList();  

}
}

class Mergesortedlists 
{
    public Node MergeSortedLists(Node head1, Node head2) 
    {

    Node result = new Node(0); 
    Node lastptr = result;
    while(true) 
    {
        if(head1 == null)
        {
            lastptr.next = head2;
            break;
        }
        if(head2 == null)
        {
            lastptr.next = head1;
            break;
        }

        if(head1.data <= head2.data)
        {
            lastptr.next = head1;
            head1 = head1.next;
        } 
        else
        {
            lastptr.next = head2;
            head2 = head2.next;
        }

        lastptr = lastptr.next;
    }
    return result.next;
    }
}

Output

1 2 3 4 4 6 7 8 9

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next

    def insert(self, newData):
        newNode = Node(newData)
        if self.head is None:
            self.head = newNode
            return

        last = self.head
        while last.next:
            last = last.next

        last.next = newNode

def mergeSortedLists(head1, head2):

    result = Node(0)
    lastptr = result
    while True:
        if head1 is None:
            lastptr.next = head2
            break
        if head2 is None:
            lastptr.next = head1
            break

        if head1.data <= head2.data:
            lastptr.next = head1
            head1 = head1.next
        else:
            lastptr.next = head2
            head2 = head2.next

        lastptr = lastptr.next

    return result.next

# Create 2 lists
head1 = LinkedList()
head2 = LinkedList()

head1.insert(1)
head1.insert(2)
head1.insert(4)
head1.insert(6)
head1.insert(9)

head2.insert(3)
head2.insert(4)
head2.insert(7)
head2.insert(8)

head1.head = mergeSortedLists(head1.head, head2.head)

head1.printList()

Output

1 2 3 4 4 6 7 8 9

Complexity Analysis

Time Complexity Analysis
In this algorithm, we are running a loop while either of the head1 or head2 will become null which will take time complexity equal to the minimum of lengths of both the list, i.e. min(O(N+M)) or in general we can consider it as O(N) time complexity

So the total worst-case time complexity for this approach to merge two sorted linked lists is min(O(N), O(M)) = O(N)

Space Complexity Analysis
In this approach we are just using two variables i.e. Nodes to store the pointers, so we are using constant extra space and we can consider it as O(1) space complexity

Time Complexity: O(N)
Space Complexity: O(1)

Approach 4 (Reversing the Linked Lists)

In this approach, we will reverse both lists. The main intuition behind this approach is that we will first create two nodes temp and res, and then reverse both lists. We will keep track of our result in the res node and the temp node is used for swapping the res node and the node which is to be added. We will add the head of the current greatest node to the result. By doing this we are building our resultant list in the reverse order.

Algorithm

  • Create two new Nodes named res and temp.
  • Initialize both res and temp with NULL.
  • Now run a while loop while head1 and head2 are not null and perform the following steps :
    • if head1‘s data>=head2‘s data, then initialize temp with head1‘s next, head1‘s next with res, res with head1, and change head1 to temp.
    • initialize temp with head2‘s next, head2‘s next with res, res with head2, and change head2 to temp.
  • Finally return the res node.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node* next; 
};
void reverse(Node *&head_ref) {
    Node *temp = NULL;
    Node *prev = NULL;
    Node *current = (head_ref);
    while(current != NULL) {
        temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    (head_ref) = prev;
}
void MoveNode(Node** destRef, Node** sourceRef) 
{ 
    Node* newNode = *sourceRef; 
    assert(newNode != NULL); 

    *sourceRef = newNode->next; 

    newNode->next = *destRef; 
    *destRef = newNode; 
}
Node* MergeSortedLists(Node* head1, Node* head2) 
{ 
    Node* res = NULL;

    Node* temp = NULL;
    reverse(head1);
    reverse(head2);

    while (head1 and head2) {
        if(head1->data>=head2->data){
            temp = head1->next;
            head1->next = res;
            res = head1;
            head1=temp;
        }
        else{
            temp = head2->next;
            head2->next = res;
            res = head2;
            head2 = temp;
        }
    }
    while(head1){
        temp = head1->next;
        head1->next = res;
        res = head1;
        head1=temp;
    }
    while(head2){
        temp = head2->next;
        head2->next = res;
        res = head2;
        head2 = temp;
    }
    return (res);
} 

void insert(Node** head_ref, int new_data) { 
    Node* newNode = new Node();
    newNode->data = new_data; 
    newNode->next = (*head_ref); 
    (*head_ref) = newNode; 
} 
void printNodes(Node *node) { 
    while (node!=NULL) { 
        cout<<node->data<<" "; 
        node = node->next; 
    } 
}

int main() 
{ 
    Node* result = NULL; 
    Node* head1 = NULL; 
    Node* head2 = NULL; 

    insert(&head1, 9);
    insert(&head1, 6);
    insert(&head1, 4); 
    insert(&head1, 2); 
    insert(&head1, 1); 

    insert(&head2, 8);
    insert(&head2, 7); 
    insert(&head2, 4); 
    insert(&head2, 3); 
    result = MergeSortedLists(head1, head2); 

    printNodes(result); 
    return 0; 
}

Output

1 2 3 4 4 6 7 8 9

Java Implementation

import java.util.*;
class Node
{
    int data;
    Node next;
    Node(int d) {data = d;
                next = null;}
}

class Main
{
Node head;
   public Node reverse(Node node)
    {
        Node prev = null;
        Node current = node;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node;
    }
public void addToTheLast(Node node)
{
    if (head == null)
    {
        head = node;
    }
    else
    {
        Node temp = head;
        while (temp.next != null)
            temp = temp.next;
        temp.next = node;
    }
}
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[])
{
    Main head1 = new Main();
    Main head2 = new Main();

    head1.addToTheLast(new Node(1));
    head1.addToTheLast(new Node(2));
    head1.addToTheLast(new Node(4));
    head1.addToTheLast(new Node(6));
    head1.addToTheLast(new Node(9));

    head2.addToTheLast(new Node(3));
    head2.addToTheLast(new Node(4));
    head2.addToTheLast(new Node(7));
    head2.addToTheLast(new Node(8));


    head1.head = new Mergesortedlists().MergeSortedLists(head1.head,head2.head);
    head1.printList();  

}
}

class Mergesortedlists 
{
    Node reverse(Node node)
    {
        Node prev = null;
        Node current = node;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node;
    }


    public Node MergeSortedLists(Node head1, Node head2) 
    {

        Node res = null;

    Node temp = null;
    head1=reverse(head1);
    head2=reverse(head2);

    while (head1!=null && head2!=null) {
        if(head1.data>=head2.data){
            temp = head1.next;
            head1.next = res;
            res = head1;
            head1=temp;
        }
        else{
            temp = head2.next;
            head2.next = res;
            res = head2;
            head2 = temp;
        }
    }
    while(head1!=null){
        temp = head1.next;
        head1.next = res;
        res = head1;
        head1=temp;
    }
    while(head2!=null){
        temp = head2.next;
        head2.next = res;
        res = head2;
        head2 = temp;
    }

        return (res);
}
}

Output

1 2 3 4 4 6 7 8 9

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:

    def __init__(self):
        self.head = None

    def reverse(self):
        prev = None
        current = self.head
        while(current is not None):
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

    def insert(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data,end=" ")
            temp = temp.next

def mergeSortedLists(head1, head2):
    res = None
    temp = None

    while (head1!=None and head2!=None):
        if(head1.data>=head2.data):
            temp = head1.next
            head1.next = res
            res = head1
            head1=temp
        else:
            temp = head2.next
            head2.next = res
            res = head2
            head2 = temp
    while(head1!=None):
        temp = head1.next
        head1.next = res
        res = head1
        head1=temp
    while(head2!=None):
        temp = head2.next
        head2.next = res
        res = head2
        head2 = temp
    return res

head1 = LinkedList()
head2 = LinkedList()

head1.insert(1)
head1.insert(2)
head1.insert(4)
head1.insert(6)
head1.insert(9)

head2.insert(3)
head2.insert(4)
head2.insert(7)
head2.insert(8)


head1.head = mergeSortedLists(head1.head, head2.head)

head1.printList()

Output

1 2 3 4 4 6 7 8 9

Complexity Analysis

Time Complexity Analysis

  • In the first step, we are reversing both the linked lists which will perform the operations equal to the lengths of the linked lists i.e. O(N) + O(M)
  • In the second step, we are running 3 loops, the first loop will perform the operations equal to the minimum of the length of both the lists, the second loop will perform the remaining operations left till the head1 becomes null and the third loop will also perform the remaining operations left till the head2 becomes null.
  • So the total time complexity taken in step two will be O(N)+O(M).

So the total worst-case time complexity for this approach to merge two sorted linked lists is O(N)+O(M)+O(N)+O(M) = 2 * O(N) + 2 * O(M) or in general we can consider it as O(N) time complexity

Space Complexity Analysis
In this approach we are just using two variables i.e. Nodes to store the pointers, so we are using constant extra space and we can consider it as O(1) space complexity

Time Complexity: O(N)
Space Complexity: O(1)

Conclusion

In this quick tutorial, we have discussed 4 different approaches to merge two sorted linked lists.

  • In Approach 1, we used simple recursion which took O(N) time complexity and O(N) auxiliary space.
  • In Approach 2, we used the dummy node method and returned the dummy.next pointer that took O(N) time complexity and O(1) auxiliary space.
  • In Approach 3, we used the local reference variable which took O(N) time complexity and O(1) auxiliary space.
  • In approach 4, we reverse the lists that took O(N) time complexity and O(1) auxiliary space.

Author

Latest articles

Largest Number Formed from an Array

Sindhuja Gudala

Fundamentals of Enhanced Interior Gateway Routing Protocol

Trapti Gupta

What is Network Hub?

Akshay Mishra