Use a dummy node to simplify list construction. Compare the heads of both lists, appending the smaller node to the merged list. When one list is exhausted, append the remainder of the other.
Recursively choose the smaller head node and set its next to the result of merging the remaining lists. Base case: if either list is empty, return the other.
""" 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()
current = dummy
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.next = list1 if list1 else list2
return dummy.next
#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
"""Helper to build a linked list from a list of values"""
dummy = ListNode()
current = dummy
for v in vals:
current.next = ListNode(v)
current = current.next
return dummy.next
def print_list(head):
"""Helper to print a linked list"""
result = []
while head:
result.append(head.val)
head = head.next
print(result)
def testcase():
"""Test Function"""
print_list(Solution().mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4])))
print_list(Solution().mergeTwoLists(build_list([]), build_list([])))
print_list(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(vals):
"""Helper to build a linked list from a list of values"""
dummy = ListNode()
current = dummy
for v in vals:
current.next = ListNode(v)
current = current.next
return dummy.next
def print_list(head):
"""Helper to print a linked list"""
result = []
while head:
result.append(head.val)
head = head.next
print(result)
def testcase():
"""Test Function"""
print_list(Solution().mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4])))
print_list(Solution().mergeTwoLists(build_list([]), build_list([])))
print_list(Solution().mergeTwoLists(build_list([]), build_list([0])))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()