[알고리즘/Python] LeetCode 21. Merge Two Sorted Lists

📑 1. 문제 이해

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

Merge Two Sorted Lists - LeetCode

이 문제는 오름차순으로 정렬된 두개의 연결리스트를 오름차순으로 정렬된 하나의 연결리스트로 합치는 문제입니다. 이때 연결리스트는 비어있을 수 있습니다. 각 연결리스트는 최대 50개의 노드를 가집니다. 노드는 음수값도 가질 수 있습니다.

☑️ 테스트케이스

문제에서 주어진 테스트 케이스는 다음과 같습니다.

 

1) Example 1: list1 = [1,2,4], list2 = [1,3,4]

    - 두 연결리스트는 길이가 같고 중복된 원소를 가집니다.

2) Example 2: list1 = [], list2 = []

    - 두 연결리스트는 모두 비어있습니다.

3) Example 3: list1 = [], list2 = [0]

    - 둘 중 하나의 연결리스트가 비어있습니다.

💡 2. 알고리즘 설계

 연결리스트의 링크를 조정해줌으로써 두 연결리스트를 합칠 수 있습니다. 

 

1. dummy head를 만들어줍니다. prev는 새롭게 만들어진 연결리스트의 마지막을 가리킵니다.

2. l1과 l2가 유효한 노드를 가리키는 동안 두 노드의 값을 비교해서 링크를 조정해줍니다. l1, l2 둘 중 값이 작은 노드를 prev.next가 가리키도록 하고,  그 노드를 가리키는 포인터를 한칸 전진합니다. l1, l2 중 하나가 None을 가리키면 즉, 두개의 연결리스트 중 하나의 끝에 도달하면 반복문을 종료합니다.

3. 만약 l1이 여전히 유효한 노드를 가리킨다면 prev.next가 l1을 가리키도록 합니다. l1이후의 노드는 이미 오름차순 정렬된 상태로 링크를 조정할 필요가 없습니다. l2가 여전히 유효한 노드를 가리킨다면 prev.next가 l2를 가리키도록합니다.

4.dummy head를 제외한 실제 head를 반환합니다.

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(float('inf'), None)
        prev = head
        while l1 and l2:
            if l1.val >= l2.val:
                prev.next = l2
                l2 = l2.next
            else:
                prev.next = l1
                l1 = l1.next
            prev = prev.next
        if l1:
            prev.next = l1
        if l2:
            prev.next = l2
        return head.next

시간 복잡도 및 공간 복잡도

시간 복잡도: O(1).   최악의 경우 포인터의 이동이 노드의 개수만큼 일어납니다.

공간 복잡도: O(1). 기존의 노드를 활용하고 링크만 조정해줍니다. 추가적인 공간이 필요하지 않습니다.

 

 ⎌ 3. 검토

1) Example 1: list1 = [1,2,4], list2 = [1,3,4]

    - prev가 list2의 4를 가리키고, l1이 4를 가리키는 채로 반복문이 종료됩니다. prev의 next가 l1을 가리키도록 합니다. 그 결과 정렬된 하나의 연결리스트가 됩니다.

 

2) Example 2: list1 = [], list2 = []

    - 반복문과 두개의 조건문 모두 실행되지 않은 채로 메소드가 종료됩니다. None이 반환됩니다.

 

3) Example 3: list1 = [], list2 = [0]

    - list1이 처음부터 비어있으므로 반복문은 실행되지 않습니다. list2의 head가 반환됩니다.

---

✅ 정리

◎ 연결리스트의 병합은 포인터를 조정함으로써 O(1) 공간복잡도로 해결할 수 있습니다.