[LeetCode] 21. Merge Two Sorted Lists

말하는 감자·2024년 11월 29일

leetcode linked list python recursion 연결 리스트 재귀 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

16/32

오늘부터 LeetCode의 자료구조와 알고리즘 문제 풀이를 본격적으로 시작하려고 합니다. 첫 번째 파트는 Linked List 자료구조입니다.

Linked List는 단독으로는 많이 등장하지 않지만, 트리나 그래프 같은 고급 자료구조를 다룰 때 자주 활용되기 때문에 기본적으로 익혀두는 것이 중요합니다. 오늘 풀 문제는 Linked List의 정말 기초적인 문제로 보이지만, 막상 풀어보니 생각보다 많이 헷갈렸습니다. 역시 기본기를 더 단단히 다질 필요가 있음을 느꼈습니다. 😞

그럼, 오늘의 문제를 함께 살펴보겠습니다.

1. 오늘의 학습 키워드

Linked List
Recursion

2. 문제: 21. Merge Two Sorted Lists

단계: Easy
주제: Linked List, Recursion
출처: https://leetcode.com/problems/merge-two-sorted-lists/description/

Description

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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

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

3. 문제 풀이

Step1. 문제 이해하기

두 개의 오름차순의 링크드 리스트 list1과 list2가 있습니다. 이 두 개의 링크드 리스트를 하나의 오름차순으로 정렬된 연결 리스트로 병합하는 문제입니다.

그런데, 저는 시작부터 약간 멈칫하는 부분이 있었습니다. 문제의 마지막 문장입니다.

Return the head of the merged linked list.

저는 이 문장을 보고,, 어? 분명 병합된 연결 리스트를 반환하는거 아냐? 왜 head를 반환하는거지?

사실.. 이것은 제가 연결 리스트를 제대로 이해하지 않았다는 것을 의미합니다.

문제에서 head를 반환하라는 것은 단순히 병합된 연결 리스트의 시작 노드를 반환하라는 의미입니다. 연결 리스트는 노드들이 포인터를 통해 서로 연결된 구조이기 때문에, 연결 리스트 전체를 반환하는 대신, 첫 번째 노드(Head)만 반환하면 나머지 노드들도 접근할 수 있습니다.

연결 리스트에서 head를 반환하는 이유

연결 리스트 구조:
- 연결 리스트는 배열처럼 모든 데이터를 한 번에 반환할 수 없습니다.
- 대신, 첫 번째 노드(head)를 통해 이후의 노드들에 접근할 수 있습니다.
효율성:
- 병합된 연결 리스트의 모든 노드를 탐색한 결과를 배열로 변환하려면 추가적인 메모리와 작업이 필요합니다.
- 하지만 head를 반환하면 추가 작업 없이 바로 연결 리스트를 사용할 수 있습니다.
문제의 요구사항:
- 문제는 연결 리스트를 반환하라고 했으므로, 연결 리스트의 시작점을 나타내는 head를 반환하는 것이 맞습니다.

즉, 문제에서 "head를 반환하라"고 명시한 것은 연결 리스트의 구조적 특성을 활용해 병합된 리스트의 시작점을 반환하는 방식으로 리스트를 나타내기 위함입니다.

문제의 입출력과 제약 조건을 확인하겠습니다.

Input:
- 두 개의 연결 리스트가 입력입니다. 문제에선 단순히 리스트로 보이지만 실제로는 ListNode 클래스를 활용한 연결 리스트입니다.
- 두 연결 리스트의 노드 개수는 0이상 50이하입니다. 아무래도 이것이 시간 복잡도에 영향을 줄것입니다. 따라서 시간 복잡도 상으로는 매우 여유있습니다.
- 노드의 값 크기는 -100이상 100이하입니다. 이것은 구현이나 시간 복잡도 설정에 큰 의미가 없습니다.
- 두 연결리스트는 내림차순이 아니라는 정보가 있습니다. 문제를 살펴보시면 오름차순으로 되어있다고 명시되어 있습니다.
Output:
- 문제에선 병합된 리스트를 반환하는 것처럼 보이지만 앞서 봤듯이 병합된 연결리스트의 head를 반환합니다.

어느 정도 문제 이해가 완료되었습니다. 이제 문제 분석하러 가보시죠!

Step2. 문제 분석하기

오름차순으로 정렬된 두 개의 연결리스트가 있습니다. 이 두 개의 연결리스트를 하나의 오름차순으로 정렬된 연결 리스트를 구하는 문제입니다.

그렇다면, 각 두 개의 연결리스트의 요소들을 서로서로 비교하면서 나아가면 되지 않을까요?

예를 들어, 아래와 같이 두 개의 연결 리스트가 있다고 가정하겠습니다(간단히 리스트로 표현하겠습니다).

list1 = [1,2,3]
list2 = [1,4,6]

list1과 list2는 연결 리스트로 표현한다면 다음과 같이 표현할 수 있습니다.

list1 = head → 1 → 2 → 3
list2 = head → 1 → 4 → 6

list1과 list2의 첫번째 요소는 같습니다. 그렇기 때문에 병합된 첫번째 노드는 1이 되겠죠? (head제외입니다)

그 다음은 2와 4입니다. 여기서 병합된 연결리스트는 2를 가리켜야 하겠죠? 이렇게 두 개의 연결 리스트의 요소를 비교하면서 더 작은 값을 이전 값의 next node로 설정하면 됩니다.

이것을 순서로 보이자면 다음과 같습니다.

head
head → 1
head → 1 → 2
head → 1 → 2 →3 → 4
head → 1 → 2 → 3 → 4 → 6

문제 분석까지 완료되었습니다.

이렇게 진행한다면 시간 복잡도는 두 연결 리스트를 순회하기 때문에 O(len(list1) + len(list2))가 될 것으로 예상됩니다.

이제 코드를 설계하러 가볼까요?

Step3. 코드 설계

해당 문제는 이렇게 두 연결리스트를 순회하면서 요소를 비교하면서 병합된 연결 리스트

반복문 설계

Head 노드 생성:
- 병합된 리스트의 시작점을 임시로 저장하기 위해 head라는 빈 노드를 생성합니다.
- start 변수를 초기화하여 병합 작업을 진행합니다.
리스트 순회:
- list1과 list2를 모두 순회하며 값을 비교합니다.
- 작은 값을 가진 노드를 병합된 리스트의 start.next에 연결하고, 해당 리스트의 다음 노드로 이동합니다.
- start 포인터도 다음 노드로 이동합니다.
남은 노드 연결:
- 한 리스트가 끝났다면, 남아 있는 다른 리스트의 노드를 병합된 리스트에 연결합니다.
Head 반환:
- head.next를 반환하여 병합된 리스트의 시작점을 반환합니다.

재귀 설계

Base Case:
- list1 또는 list2가 None이면, 남아 있는 다른 리스트를 반환합니다.
재귀적 병합:
- list1.val과 list2.val을 비교하여 더 작은 값을 가진 노드를 선택합니다.
- 선택된 노드의 next를 재귀적으로 호출하여 병합된 결과와 연결합니다.
결과 반환:
- 최종적으로 병합된 연결 리스트의 시작 노드를 반환합니다.

Step4. 코드 구현

반복문

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        head = ListNode()

        start = head
        

        while list1 and list2:
            if list1.val < list2.val:
                start.next = list1
                list1 = list1.next
            else:
                start.next = list2
                list2 = list2.next

            start = start.next
        
        if list1:
            start.next = list1
        if list2:
            start.next = list2
        
        return head.next

코드 설명:

head라는 dummy 노드를 생성하여 병합된 리스트를 임시로 저장합니다.
list1과 list2의 값을 비교하면서 순차적으로 병합 작업을 진행합니다.
비교 작업이 끝나면 남은 노드를 병합된 리스트에 연결합니다.

시간 복잡도:

두 연결 리스트를 순회하므로 시간 복잡도는 $O(n + m)$ 입니다.
여기서 $n$ 과 $m$ 은 각각 list1과 list2의 노드 개수입니다.

결과:

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

재귀

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # base case
        if list1 is None or list2 is None:
            return list1 or list2

        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2