Merge Two Sorted Lists - Python Solution

1. Introduction

"Merging Two Sorted Lists" is a fundamental problem in the realm of linked lists, particularly focusing on the manipulation and merging of sorted data structures. It tests the ability to traverse and combine two linked lists into a single sorted list, which is a common operation in data processing and algorithm design.

Problem

Given the heads of two sorted linked lists list1 and list2, the task is to merge these lists into one sorted list. The merged list should be constructed by splicing together the nodes of the first two lists. The goal is to return the head of the merged linked list.

2. Solution Steps

1. Initialize a dummy node to serve as the starting point of the merged list.

2. Maintain a current pointer to track the end of the merged list.

3. Compare the nodes of the two lists and attach the smaller node to the end of the merged list.

4. Move the current pointer and the pointer of the list from which the node was taken.

5. Repeat the process until all nodes from both lists are processed.

6. If one list is exhausted, attach the remaining nodes of the other list to the merged list.

7. Return the node next to the dummy node, which is the head of the merged list.

3. Code Program

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    current = dummy

    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    current.next = list1 or list2
    return dummy.next

# Example Usage
# Creating lists for demonstration: [1 -> 2 -> 4] and [1 -> 3 -> 4]
list1 = ListNode(1, ListNode(2, ListNode(4)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
result = mergeTwoLists(list1, list2)
# Output the list
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

Output:

[1, 1, 2, 3, 4, 4]

Explanation:

1. ListNode Class: ListNode is a basic structure representing each node in the linked list.

2. Dummy Node: A dummy node is used as a placeholder to simplify the merge logic.

3. Merging Process: The nodes from list1 and list2 are compared and the smaller one is attached to the merged list.

4. List Traversal: Both lists are traversed simultaneously, and nodes are spliced into the merged list.

5. Remaining Nodes: If one list gets exhausted before the other, the remaining nodes are directly attached.

6. Returning Result: The node following the dummy node becomes the head of the merged list, which is returned.

7. Efficient and Simple: This approach provides an efficient and straightforward way to merge two sorted linked lists.