Merge Two Doubly Linked Lists

Introduction to Merging Two Doubly Linked Lists

Merging two doubly linked lists involves combining the nodes of the two lists into a single sorted list. This can be achieved using a two-pointer technique to traverse both lists and merge them in sorted order.

---

Step-by-Step Process

Consider two doubly linked lists with the following structures before merging:

List 1: Head1 <-> 1 <-> 3 <-> 5 <-> None
List 2: Head2 <-> 2 <-> 4 <-> 6 <-> None

We want to merge these lists into a single sorted list:

Merged List: Head <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> None

Follow these steps to merge the lists:

1. Initialize Pointers: Start with two pointers, one for each list (l1 and l2).
2. Create a Dummy Node: Create a dummy node to act as the starting point for the merged list, and a current pointer to build the merged list.
3. Traverse and Merge: Compare the nodes pointed to by l1 and l2. Append the smaller node to the merged list and move the corresponding pointer one step forward. Repeat until one of the lists is exhausted.
4. Append Remaining Nodes: If any nodes remain in either list, append them to the merged list.
5. Update Previous Pointers: Traverse the merged list and update the previous pointers for each node.
6. Return Merged List: The merged list starts from the next node of the dummy node.

---

Python Program to Merge Two Doubly Linked Lists

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def merge(self, other):
        dummy = Node(0)
        current = dummy
        l1 = self.head
        l2 = other.head
        while l1 and l2:
            if l1.data <= l2.data:
                current.next = l1
                l1.prev = current
                l1 = l1.next
            else:
                current.next = l2
                l2.prev = current
                l2 = l2.next
            current = current.next
        if l1 is not None:
            current.next = l1
            l1.prev = current
        if l2 is not None:
            current.next = l2
            l2.prev = current
        self.head = dummy.next
        if self.head is not None:
            self.head.prev = None

# Example usage:
list1 = DoublyLinkedList()
list1.append(1)
list1.append(3)
list1.append(5)
print("List 1:")
list1.traverse()  # Output: 1 <-> 3 <-> 5 <-> None

list2 = DoublyLinkedList()
list2.append(2)
list2.append(4)
list2.append(6)
print("List 2:")
list2.traverse()  # Output: 2 <-> 4 <-> 6 <-> None

list1.merge(list2)
print("Merged List:")
list1.traverse()  # Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> None

This Python program defines a doubly linked list with methods for appending nodes, traversing the list, and merging two lists. The merge method merges two doubly linked lists into a single sorted list using the two-pointer technique and updates the previous pointers accordingly.