O(n)

from typing import List

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        w1 = l1
        w2 = l2

        l = ListNode(0)
        w = l

        while w1 is not None and w2 is not None:
            if w1.val < w2.val:
                w.next = ListNode(w1.val)
                w1 = w1.next
            else:
                w.next = ListNode(w2.val)
                w2 = w2.next
            w = w.next

        if w1 is not None:
            while w1 is not None:
                w.next = ListNode(w1.val)
                w1 = w1.next
                w = w.next

        if w2 is not None:
            while w2 is not None:
                w.next = ListNode(w2.val)
                w2 = w2.next
                w = w.next

        return l.next

def getList(l: List[int]) -> ListNode:
    head = None
    if not l:
        return head

    head = ListNode(l[0])
    walker = head
    for i in range(1, len(l)):
        walker.next = ListNode(l[i])
        walker = walker.next

    return head

def disp(l: ListNode) -> None:
    walker = l

    while walker is not None:
        print('-> '+str(walker.val), end = ' ')
        walker = walker.next
    print()

def main():
    l1 = getList([1, 2, 4])
    l2 = getList([1, 3, 4])

    disp(l1)
    disp(l2)

    s = Solution()
    l = s.mergeTwoLists(l1, l2)

    disp(l)

if __name__ == '__main__':
    main()