Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted linked list and return the head of the new sorted linked list.
The new list should be made up of nodes from list1 and list2.

Intuition

We are going compare nodes one by one from both of the lists and append the smaller node to a new Linked List. Initially List1 and List2 both are pointed at the HEAD of the Lists. According to the problem description, We need to select the smaller nodes from both of these Sorted Lists and Build a New Sorted Linked List (i.e. The Merged List from Two Sorted Lists).
To build a new Linked List we will follow DUMMY HEAD technique to skip edge case handling.
So we will Initialize a Dummy Node and a pointer curr pointing at the newly created dummy node (i.e. Dummy Head)

# Definition for singly-linked list.
# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
	dummy = ListNode()  # creating the dummy node
	curr = dummy  # pointing curr pointer at dummy node

Now we will iterate over both of the lists list1 and list2 and compare their Node Values. Node that has Smaller value will be appended to the new Linked List next to the Dummy Head.
This loop will be continued until any of the lists reach to the NULL.
Let's write the code first and we will visualize the output later.

dummy = ListNode()  # creating the dummy node
curr = dummy  # pointing curr pointer at dummy node
while list1 and list2:
	if list1.val < list2.val:
		curr.next = list1
		list1 = list1.next
	else:
		curr.next = list2
		list2 = list2.next
	curr = curr.next

Let's visualize the output of this above code.

As we can see, Node 1 is taken from List2 and appended to the new list. After that list2 and curr pointer moved to the next node. Let's repeat the process until either list1 or list2 reaches at the end of the List NULL

list1 pointer has reached at the NULL, so we will be out of the loop now. But we have remaining items in the list2. So we will just append the while chain of list2 to the new linked list like this

see the code bellow

# we are noe out of the while loop
# collecting the remaining items
# first checking for list1
if list1:
	curr.next = list1
if list2:
	curr.next = list2

But we can also use a shortcut in python like one-liner curr.next = list1 or list2. Because only one of the lists can have remaining items. So the outcome will be

Complete Code Snippet

class Solution:
	def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
		dummy = ListNode()
		curr = dummy
		while list1 and list2:
			if list1.val < list2.val:
				curr.next = list1
				list1 = list1.next
			else:
				curr.next = list2
				list2 = list2.next
			curr = curr.next
		# collect the remaining items
		curr.next = list1 or list2
		# return the read HEAD of the new linked list, not dummy head
		return dummy.next

That's it for now. Thanks for stopping by!

Connect with me on