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.

Sorted merge of two sorted doubly linked list

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 and l2 to the heads of the two lists. It also initializes a pointer back 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.