Merge Two Singly Linked Lists

Merging Two Singly Linked Lists

Merging two singly 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 singly 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. Return Merged List: The merged list starts from the next node of the dummy node.

---

Python Program to Merge Two Singly Linked Lists

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

class SinglyLinkedList:
    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

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

def merge_lists(l1, l2):
    dummy = Node(0)
    current = dummy
    while l1 and l2:
        if l1.data <= l2.data:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 if l1 else l2
    return dummy.next

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

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

merged_head = merge_lists(list1.head, list2.head)
merged_list = SinglyLinkedList()
merged_list.head = merged_head
print("Merged List:")
merged_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

This Python program defines a singly linked list with methods for appending nodes and traversing the list. The merge_lists function merges two singly linked lists into a single sorted list using the two-pointer technique.