Use a dummy node to simplify edge cases. Compare the heads of both lists, appending the smaller node to the merged list. Once one list is exhausted, append the remainder of the other.
Base case: if either list is empty, return the other. Compare the heads — attach the smaller one and recurse on its next with the other list.
""" 0021.1 - Merge Two Sorted Lists - Solution 1 - Iterative with Dummy Node """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
"""Merge Two Sorted Lists Function"""
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
curr.next = list1 or list2
return dummy.next
#####################################################################################
# Functions
#####################################################################################
def build_list(values):
"""Helper to build a linked list from a list of values"""
dummy = ListNode()
curr = dummy
for v in values:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def list_to_array(head):
"""Helper to convert a linked list to a list"""
result = []
while head:
result.append(head.val)
head = head.next
return result
def testcase():
"""Test Function"""
print(list_to_array(Solution().mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4]))))
print(list_to_array(Solution().mergeTwoLists(build_list([]), build_list([]))))
print(list_to_array(Solution().mergeTwoLists(build_list([]), build_list([0]))))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0021.2 - Merge Two Sorted Lists - Solution 2 - Recursive """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
"""Merge Two Sorted Lists Function"""
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
#####################################################################################
# Functions
#####################################################################################
def build_list(values):
"""Helper to build a linked list from a list of values"""
dummy = ListNode()
curr = dummy
for v in values:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def list_to_array(head):
"""Helper to convert a linked list to a list"""
result = []
while head:
result.append(head.val)
head = head.next
return result
def testcase():
"""Test Function"""
print(list_to_array(Solution().mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4]))))
print(list_to_array(Solution().mergeTwoLists(build_list([]), build_list([]))))
print(list_to_array(Solution().mergeTwoLists(build_list([]), build_list([0]))))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()