Leetcode Python - 21. Merge Two Sorted Lists

Leetcode #21 - Merge Two Sorted Lists

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. linkedlist를 집중적으로 풀어보겠습니다.

리트코드의 문제 21 ‘Merge Two Sorted Lists’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 dummy listNode를 만드는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1 and not l2:
            return l1
        elif not l1:
            return l2
        elif not l2:
            return l1
        
        dummy = head = ListNode(0)
        h1 = l1
        h2 = l2
        
        while h1 or h2:
            node = ListNode(0)
            if h1 is None:
                node.val=h2.val
                h2 = h2.next
            elif h2 is None:
                node.val=h1.val
                h1 = h1.next
            else:
                if h1.val <= h2.val:
                    node.val = h1.val
                    h1 = h1.next
                else:
                    node.val = h2.val
                    h2 = h2.next
            head.next = node
            head = head.next
        
        return dummy.next

시간복잡도는 O(m+n) : 첫번째 linked list의 길이 m, 두번째 linked list의 길이 n 일때, 두 linked list를 순회

공간복잡도는 O(m+n) : m+n크기의 linked list를 만듦