Merge Two Sorted Singly-linked List

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


def mergeTwoLists(list1, list2):
    # Initialize a dummy node to simplify the merging process
    dummy = ListNode()
    current = dummy # current and dummy store the same address pointing to dummy object

    # Traverse both lists simultaneously and merge
    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 now store it's current.next address, not equal to dummy object, actually it points to dummy.next object

    # Attach the remaining nodes of the non-empty list
    if list1:
        current.next = list1
    elif list2:
        current.next = list2

    # Return the head of the merged list
    return dummy.next


# Helper function to print the linked list
def printLinkedList(head):
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")


# Sample linked list creation
def createLinkedList(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Sample data
list1_values = [1, 3, 5]
list2_values = [2, 4, 6]

# Create sample linked lists
list1 = createLinkedList(list1_values)
list2 = createLinkedList(list2_values)

# Merge the two lists
merged_list_head = mergeTwoLists(list1, list2)

# Print the merged list
print("Merged Linked List:")
printLinkedList(merged_list_head)
# 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None