개요

LeetCode #21, Merge Two Sorted List 문제를 풀어봅니다.

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = [] Output: []

Example 3:

Input: l1 = [], l2 = [0] Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

l1, l2 값을 비교해서 작은 값을 왼쪽으로 보내고, l1은 다음 것으로 넘어가서 계속 돕니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # No l1 or l2 exist + l1 > l2
        if (not l1) or (l2 and l1.val > l2.val):
            # smaller one -> left
            l1, l2 = l2, l1
        if l1:
            # next linked list 
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1