Merge Two Sorted Lists

두 개의 연결 리스트를 정렬해서 하나로 합치는 문제

https://leetcode.com/problems/merge-two-sorted-lists/

# 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:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            if l1.val < l2.val:
                head = l1
                l1 = l1.next
            else:
                head = l2
                l2 = l2.next

            return self.__mergeTwoLists( head, head, l1, l2 )


    def __mergeTwoLists( self, head, runner, l1, l2 ):
        if l1 is None:
            runner.next = l2
            return head
        elif l2 is None:
            runner.next = l1
            return head
        else:
            if l1.val < l2.val:
                runner.next = l1
                l1 = l1.next
            else:
                runner.next = l2
                l2 = l2.next

            return self.__mergeTwoLists( head, runner.next, l1, l2 )