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

- If
- 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:

#includeusing 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.

[forminator_quiz id=”5095″]

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).