Merge two sorted linked lists into one sorted linked list

Merging two sorted linked lists involves combining all nodes present in each of the two input linked lists into a single linked list while maintaining their sorted order.

To accomplish this, we need consume the smallest head node among both the linked lists and add it to the final list. We continue the process until all nodes in both the linked lists are added to the merged sorted linked list. This approach ensures that the new merged list preserves the sorted order while re-using all nodes from the original two lists.

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

def merge_two_lists(l1, l2):
    # Create a dummy node as the starting point of the merged list
    dummy = Node()
    current = dummy

    # Loop until either of the input lists becomes empty
    while l1 and l2:
        if l1.value <= l2.value:
            # If value in l1 is smaller, link current node to l1
   = l1
            l1 =
            # If value in l2 is smaller, link current node to l2
   = l2
            l2 =

        # Move the current pointer forward
        current =

    # Append the remaining elements of l1 or l2 (if any) to the merged list
    if l1: = l1
    else: = l2

    # Return the merged list starting from the dummy's next node

With each iteration in the loop, we move one head node from l1 or l2 to the merged list. When one of l1 or l2 becomes empty, we just add the remainder to the merged list directly.