Sorted merge of two sorted doubly circular linked lists

Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

Problem Statement

In this problem, we are given two sorted doubly circular linked lists containing n and m number of nodes, respectively. Our task is to merge the two lists such that the resultant doubly circular linked list is also in sorted order.

Problem Statement Understanding

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

If the given sorted doubly circular linked lists are:
list 1:

list 2:

  • According to the problem statement, we need to merge list 1 and list 2 in such a way that the final merged list is in the sorted order.
  • After merging list 1 and list 2, our final merged sorted doubly circular linked list will be:

Taking another example, if the linked lists are:

list 1:

list 2:

  • In this case, our final sorted doubly circular linked list after merging list 1, and list 2 will be:

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think 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.

Approach

Our approach will be straightforward:

  • Basically, first, we will find the node, which will be the last node of our final merged doubly circular linked list.
    • As we know that our two given doubly circular linked list are sorted, so one thing is clear, that the last node of our final merged doubly circular linked list will be one which is having greater value among the last nodes of the two doubly circular linked list.
    • We will keep track of this node using a pointer, say last_node.
  • Now we will make the last nodes of the given doubly circular linked lists point to NULL.
  • Then after that we will merge the two doubly circular linked list in the same way we merge two sorted doubly linked list.
    • If you are not aware of how to merge two sorted doubly circular linked list, checkout our article [Merge two sorted doubly linked list]().
  • After merging the two sorted doubly linked list, we will make the merged list circular using the last_node.
  • And finally, we will have our sorted merged doubly circular linked list.

Let’s see the algorithm.

Algorithm

  • Let h1 be a pointer pointing to the head node of the first doubly circular linked list, and h2 be the pointer pointing to the head node of the second list.
  • If h2 is NULL, return h1.
  • If h1 is NULL, return h2.
  • Suppose lst1 and lst2 are the last nodes of the two doubly circular linked lists, respectively.
    • lst1 and lst2 can be obtained by the previous links of the first nodes of the respective lists.
  • Get a pointer to the node, which will be the last node of the final resultant linked list result.
    • If lst1→data is less than lst2→data, then last_node = lst2.
    • Else, last_node = lst1.
  • Now update lst1→next = lst2→next = NULL.
  • We will now merge the two lists as two sorted doubly linked lists are being merged.
  • Let the first node of the final sorted doubly circular linked list be ResHead.
  • Finally, update the *prev of ResHead to last_node and next of last_node to ResHead.
  • At the end, return ResHead.

Dry Run

Code Implementation:

#include 
using namespace std;

/* Node structure of a doubly linked list node */
struct Node {
    int data;
    Node *next, *prev;
};

/* Using this function we will be inserting a new node in the list */
void insert(Node** head, int data)
{
    Node* new_node = new Node;
    new_node->data = data;
    if (*head == NULL) {
        new_node->next = new_node;
        new_node->prev = new_node;
    }

    else {

        Node* last = (*head)->prev;
        new_node->next = *head;
        new_node->prev = last;
        last->next = (*head)->prev = new_node;
    }

    *head = new_node;
}

/* Using this function we will be merging two sorted doubly linked list */
//merge2SortedDLL stands for merge two sorted doubly linked list
Node* merge2SortedDLL(Node* l1, Node* l2)
{
    if (!l1)
        return l2;

    if (!l2)
        return l1;

    if (l1->data < l2->data) {
        l1->next = merge2SortedDLL(l1->next, l2);
        l1->next->prev = l1;
        l1->prev = NULL;
        return l1;
    }
    else {
        l2->next = merge2SortedDLL(l1, l2->next);
        l2->next->prev = l2;
        l2->prev = NULL;
        return l2;
    }
}

/* Using this function we will be merging two sorted doubly circular linked list */
//merge2SortedDCLL stands for merge two sorted doubly circular linked list
Node* merge2SortedDCLL(Node* h1, Node* h2)
{
    if (!h1)
        return h2;

    if (!h2)
        return h1;

    Node* last_node;
    if (h1->prev->data < h2->prev->data)
        last_node = h2->prev;
    else
        last_node = h1->prev;

    h1->prev->next = h2->prev->next = NULL;

    Node* ResHead = merge2SortedDLL(h1, h2);

    
    ResHead->prev = last_node;
    last_node->next = ResHead;

    return ResHead;
}

/* Using this function we will be printing the linked list content */
void PrintingList(Node* head)
{
    Node* temp = head;

    while (temp->next != head) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << temp->data << " "<

						 

Output

Original linked list 1:
1 3 5 7
Original linked list 2:
2 4 6 8
Final Sorted List:
1 2 3 4 5 6 7 8

Time Complexity: O(n+m), as each list is traversed completely.

So, in this article, you have learned how to merge two sorted doubly circular linked lists into a single sorted doubly circular linked list. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post Merge two sorted linked lists such that the merged list is in reverse order
Next post Reverse a Doubly Linked List

Leave a Reply

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