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
self.next = 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
current.next = l1
l1 = l1.next
else:
# If value in l2 is smaller, link current node to l2
current.next = l2
l2 = l2.next
# Move the current pointer forward
current = current.next
# Append the remaining elements of l1 or l2 (if any) to the merged list
if l1:
current.next = l1
else:
current.next = l2
# Return the merged list starting from the dummy's next node
return dummy.next
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.