[DSA][Linked List] 02. Merge Two Sorted Lists

LeetCode 21

 

02. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

 

 

[질문하기]

- 두 리스트 중 하나가 빈 리스트일 수도 있나요? 그럴 경우 어떻게 처리해야 하나요?

 

 

[아이디어]

- 두 연결 리스트를 순회하면서 둘 중에 더 작은 값을 가진 노드를 먼저 붙여나간다.

 

 

[풀이 1] Linked List

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = cur = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        cur.next = list1 or list2
    
        return head.next

두 연결 리스트를 순회하면서 둘 중에 더 작은 값을 가진 노드를 먼저 붙여나간다. 이 과정을 한 리스트가 끝날 때까지 반복한 후, 남아있는 다른 리스트를 결과 리스트에 그대로 붙인다. 알고리즘 자체는 간단하지만, 연결리스트에 대한 이해가 필요하기 때문에 구현하는 쪽이 조금 더 까다로울 수 있다.

 

⏱️ 시간복잡도

두 리스트의 모든 노드를 한 번씩 순회하면서 .next 포인터만 변경하므로, 시간 복잡도는 O(n + m)이다. (n과 m은 각각 list1과 list2의 길이)

🧠 공간복잡도

추가적인 노드 생성 없이 고정된 변수들만 사용하므로, 공간 복잡도는 O(1)이다.