Merge Two Unsorted Linked Lists To Get A Sorted List

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

Problem Statement

In this problem, we are given two unsorted linked lists, and we have to merge these two linked lists to get a sorted linked list.

Prerequisites: Bubble sort on linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Let’s say the given linked lists are :
List1 = head β†’ 1 β†’ 6 β†’ 10 β†’ NULL ,

List2 = head β†’ 5 β†’ 3 β†’ 9 β†’ NULL

  • So now, according to the problem statement, the given linked lists List1 and List2 are unsorted, and we need to merge them to get a sorted linked list.
  • After merging the linked lists, we need to return the head of the merged linked list.
  • After merging the two linked lists in the above example, the sorted linked lists will be head β†’ 1 β†’ 3 β†’ 5 β†’ 6 β†’ 9 β†’ 10 β†’ NULL.

The linked list will be sorted in ascending order.

Some more Examples

Example 1:
Input:
List1 = head β†’ 4 β†’ 50β†’ 12 β†’ NULL
List2 = head β†’ 10 β†’1β†’ 60 β†’ NULL

Output :
head β†’ 1 β†’ 4 β†’ 10β†’12 β†’ 50 β†’ 60

Example 2:
Input:
List 1 = head β†’ 10 β†’ 20 β†’ 60 β†’ NULL
List 2 = head β†’ 10 β†’ 50 β†’ 30 β†’ NULL

Output:
head β†’10 β†’ 10 β†’ 20 β†’ 30 β†’ 50 β†’ 60 β†’ NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Naive Approach

The naive approach to solve this problem is to first sort the two linked lists and then merge these sorted linked lists into one linked list in increasing order.

Time Complexity
O(N2 + M2 + (N+M)), where M and N are the lengths of the linked lists. We are first sorting both the lists. Sorting a list takes quadratic time (using bubble sort for sorting). Then we will be merging the two sorted list which will take O(N+M) time. Hence, the total time complexity will be O(N2 + M2 + (N+M)).

Space Complexity:
0(1), We are using only a constant amount of extra space.

Note: To see how to merge two sorted linked lists in one linked list in increasing order, check out this article.

Efficient Approach

In the efficient approach, we will first concatenate the two given linked lists and then sort the final concatenated linked list by using a sorting algorithm.

Here we will be using bubble sort to sort the linked list. To see how bubble sort works on a linked list, check out this article.

Algorithm

The algorithm of this problem is below:
1) First, we will concatenate the two lists.

  • In the first list, we will traverse the list until we reach its tail, and after reaching the tail, we will point the next of the tail node to the head node of the second list, storing the concatenated in the first list.
    2) Then, we will sort this merged list (we will use bubble sort).
  • While sorting, if nodeβ†’nextβ†’data is less than nodeβ†’data, then we will swap the data.

Dry Run

Code Implementation


#include<stdio.h>
#include<stdlib.h>

struct node {
    int data;
    struct node* next;
};
 
// Function to print the linked list
void setData(struct node* head)
{
    struct node* tmp;
 
    // Store the head of the linked
    // list into a temporary node*
    // and iterate
    tmp = head;
 
    while (tmp != NULL) {
 
        printf("%d->",tmp->data);
        tmp = tmp->next;
    }
}
 
// Function takes the head of the
// LinkedList and the data as
// argument and if no LinkedList
// exists, it creates one with the
// head pointing to first node.
// If it exists already, it appends
// given node at end of the last node
struct node* getData(struct node* head, int num)
{
 
    // Create a new node
    struct node *temp = (struct node *) malloc(sizeof(struct node));
    struct node* tail = head;
 
    // Insert data into the temporary
    // node and point it's next to NULL
    temp->data = num;
    temp->next = NULL;
 
    // Check if head is null, create a
    // linked list with temp as head
    // and tail of the list
    if (head == NULL) {
        head = temp;
        tail = temp;
    }
 
    // Else insert the temporary node
    // after the tail of the existing
    // node and make the temporary node
    // as the tail of the linked list
    else {
 
        while (tail != NULL) {
 
            if (tail->next == NULL) {
                tail->next = temp;
                tail = tail->next;
            }
            tail = tail->next;
        }
    }
 
    // Return the list
    return head;
}
 
// Function to concatenate the two lists
struct node* mergelists(struct node** head1,
                 struct node** head2)
{
 
    struct node* tail = *head1;
 
    // Iterate through the head1 to find the
    // last node join the next of last node
    // of head1 to the 1st node of head2
    while (tail != NULL) {
 
        if (tail->next == NULL
            && head2 != NULL) {
            tail->next = *head2;
            break;
        }
        tail = tail->next;
    }
 
    // return the concatenated lists as a
    // single list - head1
    return *head1;
}
 
// Sort the linked list using bubble sort
void sortlist(struct node** head1)
{
    struct node* curr = *head1;
    struct node* temp = *head1;
 
    // Compares two adjacent elements
    // and swaps if the first element
    // is greater than the other one.
    while (curr->next != NULL) {
 
        temp = curr->next;
        while (temp != NULL) {
 
            if (temp->data < curr->data) {
                int t = temp->data;
                temp->data = curr->data;
                curr->data = t;
            }
            temp = temp->next;
        }
        curr = curr->next;
    }
}
 
// Driver Code
int main()
{
    struct node* head1;
    struct node* head2;
 
    head1 = NULL;
    head2 = NULL;
 
    // Given Linked List 1
    head1 = getData(head1, 40);
    head1 = getData(head1, 72);
    head1 = getData(head1, 50);
 
    // Given Linked List 2
    head2 = getData(head2, 20);
    head2 = getData(head2, 11);
    head2 = getData(head2, 8);
    head2 = getData(head2, 1);
 
    // Merge the two lists
    // in a single list
    head1 = mergelists(&head1,
                       &head2);
 
    // Sort the unsorted merged list
    sortlist(&head1);
 
    // Print the final
    // sorted merged list
    setData(head1);
    return 0;
}
public class Prepbytes {

    static node head1 = null;
    static node head2 = null;

    static class node {
        int data;
        node next;
    };

    static void printList(node head) {
        node tmp;

        tmp = head;

        while (tmp.next != null) {
            System.out.print(tmp.data + " -> ");
            tmp = tmp.next;
        }
        System.out.println(tmp.data );
    }

    static node AddNode(node head, int num) {
        // Creating a new node
        node temp = new node();
        node tail = head;

        temp.data = num;
        temp.next = null;

        // If head is null then create linked list
        // with temp as tail and head of the linked list
        if (head == null) {
            head = temp;
            tail = temp;
        }

        // Else insert the temp node
        // after the tail of the existing
        // node and make the temp node
        // as the tail of the linked list
        else {
            while (tail != null) {
                if (tail.next == null) {
                    tail.next = temp;
                    tail = tail.next;
                }
                tail = tail.next;
            }
        }

        // Return the list
        return head;
    }

    // This function will concatenate
    // the two linked list
    static node concatenateList() {
        node tail = head1;

        while (tail != null) {
            if (tail.next == null && head2 != null) {
                tail.next = head2;
                break;
            }
            tail = tail.next;
        }

        return head1;
    }

    // This function will sort the linked list
    static void sort() {
        node current = head1;
        node temp = head1;

        // Compares the elements
        // If node->next->data is less than node->data
        // then we will swap the data.
        while (current.next != null) {
            temp = current.next;
            while (temp != null) {
                if (temp.data < current.data) {
                    int t = temp.data;
                    temp.data = current.data;
                    current.data = t;
                }
                temp = temp.next;
            }
            current = current.next;
        }
    }

    public static void main(String[] args) {
        // First linked list
        head1 = AddNode(head1, 1);
        head1 = AddNode(head1, 6);
        head1 = AddNode(head1, 10);
        System.out.println("List1:");
        printList(head1);
        // Second Linked list
        head2 = AddNode(head2, 5);
        head2 = AddNode(head2, 3);
        head2 = AddNode(head2, 9);
        System.out.println("List2:");
        printList(head2);

        head1 = concatenateList();

        sort();
        System.out.println("Final merged list:");
        printList(head1);
    }
}
class node:

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

def setData(head):

    tmp = head

    while (tmp != None):
        print(tmp.data,
            end = " -> ")
        tmp = tmp.next

def getData(head, num):

    temp = node(-1)
    tail = head
    temp.data = num
    temp.next = None

    if (head == None):
        head = temp
        tail = temp

    else:
        while (tail != None):
            if (tail.next == None):
                tail.next = temp
                tail = tail.next
            tail = tail.next

    return head

def mergelists(head1,head2):

    tail = head1
    while (tail != None):
        if (tail.next == None
            and head2 != None):
            tail.next =head2
            break
        tail = tail.next

    return head1

def sortlist(head1):

    curr = head1
    temp = head1

    while (curr.next != None):
        temp = curr.next
        while (temp != None):
            if (temp.data < curr.data):
                t = temp.data
                temp.data = curr.data
                curr.data = t
            temp = temp.next
        curr = curr.next

if __name__ == '__main__':

    head1 = None
    head2 = None

    head1 = getData(head1, 1)
    head1 = getData(head1, 6)
    head1 = getData(head1, 10)

    head2 = getData(head2, 5)
    head2 = getData(head2, 3)
    head2 = getData(head2, 9)

    head1 = mergelists(head1,head2)

    sortlist(head1)
    setData(head1)

Output

List1:
1 -> 6 -> 10
List2:
5 -> 3 -> 9
Final merged list:
1 -> 3 -> 5 -> 6 -> 9 -> 10

Time Complexity
O((N+M)2), where M and N are the lengths of the linked lists. We are merging given linked lists and iterating the merged list using nested loops to perform bubble sort. The time complexity of bubble sort is O((list.length)2). Hence, the time complexity will be O(((N+M)2).

Space Complexity
[forminator_quiz id=”5852″]

Note: Also note that to reduce the time complexity, we can use merge sort instead of bubble sort. Merge sort will have a time complexity of O(N * logN), whereas bubble sort has complexity of O(N2).

So, in this blog, we have tried to explain **how you can merge two unsorted linked lists to get a sorted list**. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *