[Leetcode 아주 상세한 문제풀이] 21. Merge Two Sorted Lists - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 21번 문제 Merge two sorted lists 다.

우선 문제를 살펴보자.

 

리트코드 21번 문제 Merge two sorted lists 링크

Merge Two Sorted Lists - LeetCode

Merge Two Sorted Lists - LeetCode

 

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.

 

 

문제 설명

문제를 간략히 살펴보자. 우리는 두 개의 정렬된 리스트 list1과 list2를입력값으로 받는다. 이때 입력받은 두 리스트를 서로 합쳐 하나의 정렬된 리스트로 만들어야 한다. 하나로 합친 정렬된 리스트를 아웃풋으로 리턴하는게 목적이다.

예를 들어 문제 예시에서 주어진 것처럼 list1은 [1,2,4] 그리고 list2는[1,3,4]로 주어졌다 이때 이 두 리스트를 합치면 [1,2,4,1,3,4]가 된다. 문제에서 요구하는 바와 같이 합쳐진 리스트를 정렬해주면 [1,1,2,3,4,4]와 같은 답을 얻을 수 있다. 이때 중요한 것은 각리스트는 서로 연결되어 있으므로 (linked), 이를 잘라 다시 붙여 하나의 합쳐진 리스트로 만들어야 한다는 점이다. 문제가 매우 명확하기 때문에 이해하기 어렵지 않을 것이다.

곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 iterative approach를 이용할 것이다.

예를 들어 문제 예시 1번에서 주어진 것 처럼 list1=[1,2,4]와 list2=[1,3,4]가 주어졌다고 생각해보자.

우선 우리는 두 리스트를 합칠 dummy 리스트를 하나 만들어 준다.

그리고 각 리스트에 포인터를 하나씩 두어 처음부터 탐색을 할 것이다.

아래와 같이 각 리스트의 head에 포인터를 위치시킨다.

그리고 현재 포인터가 위치하고 있는 값을 서로 비교한다.

이 경우 값이 같기 때문에 편의상 P2가 가리키고 있는 값을 dummy 리스트에 넣어둔다.

 

 

그리고 dummy 리스트에 넣어준 값을 가리키고 있는 포인터를 하나 오른쪽으로 옮긴다.

그리고 두 포인터를 다시 비교해주는데, 비교하는 두 값 중 더 작은 값을 dummy 리스트에 넣어준다.

이 과정을 통해 합쳐진 리스트에서 값들이 오름차순 배열이 되기 때문이다.

동시에 dummy 리스트에 넣어준 값을 가리키고 있는 포인터를 하나씩 오른쪽으로 옮긴다.

그렇게 되면 아래 그림과 같이 포인터가 이동하게 된다.

 

최종적으로 마지막 단계에서 list1의 4와 list2의4와 비교되어 list2의 4가 dummy 리스트에 들어간다.

그리고 더 이상 비교할 대상이 없다면 그 값들은 이미 dummy 리스트에 들어간 값보다 큰 값들이므로,

우리는 남아있는 값들을 dummy 리스트 마지막에 추가해주면 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

문제의 조건에 따라 single-linked list를 위한 클래스를 정의해준다 (line 1)

self.val은 현재 값을, self.next는 링크의 다른 값을 가리킨다 (line 4-5)

연결된 (linked) 리스트 두개를 입력받을 함수를 정의해 준다 (line 7)

그리고 그 두 리스트를 합칠 dummy 리스트를 하나 만들어준다 (line 9)

여기서 -1은 dummy 리스트를 위한 임의 값이다.

그리고 current라는 포인터를 그 dummy 리스트에 위치시킨다 (line 11)

앞서 설명한대로 우리는 list1과 list2를 포인터를 이용해 탐색해 나갈것이다.

우선 list1과 list2가 존재하는 동안 while loop를 돌린다 (line 14)

그리고 각 리스트에서 포인터가 가리키고 있는 값을 서로 비교하는데 (line 15)

만약 list2의 값이 list1 값 보다 크다면 list1 값을 dummy 리스트에 넣고 포인터를 오른쪽으로 한 칸 옮긴다 (line 16-17)

반대로 list2 값이 list1 값 보다 작다면 list2 값을 dummy 리스트에 넣고 포인터를 오른쪽으로 한 칸 옮긴다 (line 18-19)

이 비교를 마치고 나면 dummy 리스트에는 list1과 list2의 값 중 더 작은 값이 들어가있다.

우리는 그 다음 비교를 위해 dummy 리스트의 포인터 (current)를 오른쪽으로 한 칸 옮겨준다 (line 21)

이 과정을 반복하다보면 결국 list1과 list2 중 한 쪽이 먼저 탐색을 마치게 된다.

즉, 두 리스트 중 하나는 더 이상 비교할 수 있는 값이 남아있지 않게 된다.

이 값들은 비교하고 있는 리스트의 값들보다 큰 값들이기 때문에 마지막에 남게 된 것이다.

따라서 이 값들을 dummy 리스트 마지막에 넣어준다 (line 24-28)

우리가 원하는 것은 "정렬된" 합쳐진 리스트이므로 dummy 리스트를 리턴해준다.

 

 

문제 풀이 코드

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Create a dummy node
    dummy = ListNode(-1)
    # Pointer to the current node in the merged list
    current = dummy
    
    # While both lists are not empty
    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # If list1 is not empty, append it
    if list1:
        current.next = list1
    # If list2 is not empty, append it
    if list2:
        current.next = list2
    
    return dummy.next
 

21. Merge Two Sorted Lists