merge.py

from typing import Optional


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def list(l: list) -> Optional[ListNode]:
    if not l:
        return None
    root = ListNode(l[0])
    cur = root
    for i in l[1:]:
        cur.next = ListNode(i)
        cur = cur.next
    return root


def print_list(l: Optional[ListNode]) -> None:
    while l:
        print(l.val, end=" ")
        l = l.next
    print()


def merge(left: Optional[ListNode], right: Optional[ListNode]) -> Optional[ListNode]:
    root = ListNode(0)
    cur = root

    while True:
        match [left, right]:
            case [None, None]:
                break
            case [None, _]:
                cur.next = right
                cur = cur.next
                right = right.next
            case [_, None]:
                cur.next = left
                cur = cur.next
                left = left.next
            case [_, _]:
                if left.val < right.val:
                    cur.next = left
                    cur = cur.next
                    left = left.next
                else:
                    cur.next = right
                    cur = cur.next
                    right = right.next

    return root.next


print_list(merge(list([1, 3, 5]), list([2, 4, 6])))