  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# 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 */
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = new_node;
new_node->prev = new_node;
}

else {

new_node->prev = last;
}

}

/* 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;

}

/* Using this function we will be printing the linked list content */
{

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**