Sorted merge of two sorted doubly circular linked lists

Last Updated on November 21, 2022 by Prepbytes

In the previous articles, we have already seen different implementations on circular singly linked list and circular doubly linked list. Now let’s just look into an approach on how to merge two circular linked list.

How to Merge Two Circular Linked List

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.

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 on how to merge two circular linked list

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 on how to merge two circular linked list

• 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 on how to merge two circular linked list

## Code Implementation on how to merge two circular linked list

#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 of how to merge two circular linked list:** O(n+m), as each list is traversed completely.

**Conclusion**

So, in this article, We learnt how to merge of two circular linked lists, even though we are aware about how a normal linked list can be merged, the approach of circular linked is different.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)](https://mycode.prepbytes.com/interview-coding/practice/linked-list “Prepbytes (Linked List)”)

## FAQs

**1. What is a circular linked list?**
A circular linked list is a structured collection of various elements which are connected to form a shape of circle with no null at the end.

**2. What are the applications of circular linked lists?**
A circular linked list can be used for computer resource management and also used for implementing advanced data structures such as fibonacci heap.

**3. How do you find the circular linked list?**
We will store the header node into some other variable and traverse through the list, if we will get null at any part of list then it is not circular linked list and if no then it is a circular linked list.