Sorted merge of two sorted doubly linked lists
The problem at hand is to merge two sorted doubly linked lists into a single sorted doubly linked list. The task involves combining the elements of two sorted linked lists while maintaining their sorted order.
Problem Statement
Given two sorted doubly linked lists, the objective is to merge them into a single sorted doubly linked list. The result should be a new doubly linked list that contains all the elements from both lists while preserving their order.



Idea to Solve
The basic idea to solve this problem is to iterate through both linked lists, comparing the current nodes of each list, and merging them into a new sorted linked list. At each step, you choose the smaller element from the current nodes of the two lists and add it to the new list. Then, you move the respective pointer in the list containing the smaller element to the next node.
Pseudocode
Here's the pseudocode that outlines the algorithm to merge two sorted doubly linked lists:
class LinkNode:
int data
LinkNode next
LinkNode prev
class DoublyLinkedList:
LinkNode head
function mergeList(second):
If head is null or second is null or second.head is null or head == second.head:
Return
Initialize l1 with head of the current list
Initialize l2 with head of the second list
Initialize back with null
If l1.data > l2.data:
Set head to l2
While l1 is not null and l2 is not null:
If l1.data >= l2.data:
If back is not null:
Set back.next to l2
Set l2.prev to back
Set back to l2
Move l2 to l2.next
Else:
If back is not null:
Set back.next to l1
Set l1.prev to back
Set back to l1
Move l1 to l1.next
If l1 is not null:
Set back.next to l1
Set l1.prev to back
If l2 is not null:
Set back.next to l2
Set l2.prev to back
Set second.head to null
Create two DoublyLinkedList objects
Insert nodes into both objects
Display the original linked lists
Merge the two lists using the mergeList function
Display the merged linked list and an empty second list
Algorithm Explanation
- The
mergeList
function checks for corner cases such as empty lists, invalid second list, or both lists pointing to the same object. If any of these cases is true, it returns without performing the merge operation. - It initializes pointers
l1
andl2
to the heads of the two lists. It also initializes a pointerback
that will keep track of the last node in the merged list. - The algorithm iterates through the two lists while comparing their current nodes' data. It chooses the smaller
data and adds that node to the merged list. The
back
pointer is used to link the nodes together in the merged list. - After the loop, if there are remaining nodes in either list, they are added to the merged list, and the second list's head is set to null.
- Finally, the algorithm returns the merged list.
Code Solution
-
1) Sorted merge of two sorted doubly linked lists in java
2) Sorted merge of two sorted doubly linked lists in c++
3) Sorted merge of two sorted doubly linked lists in c
4) Sorted merge of two sorted doubly linked lists in golang
5) Sorted merge of two sorted doubly linked lists c#
6) Sorted merge of two sorted doubly linked lists in php
7) Sorted merge of two sorted doubly linked lists in python
8) Sorted merge of two sorted doubly linked lists in ruby
9) Sorted merge of two sorted doubly linked lists in scala
10) Sorted merge of two sorted doubly linked lists in swift
11) Sorted merge of two sorted doubly linked lists in kotlin
12) Sorted merge of two sorted doubly linked lists in node js
13) Sorted merge of two sorted doubly linked lists in vb.net
14) Sorted merge of two sorted doubly linked lists in typescript
Time Complexity
Merging two sorted linked lists requires visiting each node once, so the time complexity is O(N), where N is the total number of nodes in both lists.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment