[leetcode] 21. 두 정렬 리스트의 병합 (Merge Two Sorted Lists)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a 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]

 

생각과정

두 리스트의 데이터를 하나씩 꺼내서 배열에 담고, 그 배열을 정렬한 다음 새로운 연결리스트에 담는다.

 

풀이

내 풀이 코드

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    # 정렬하기 위한 배열
    list = []

    # 데이터 배열에 담기
    while l1:
        list.append(l1.val)
        l1 = l1.next
    while l2:
        list.append(l2.val)
        l2 = l2.next

    temp = None
    head = None  # 새로 만든 리스트

    for val in sorted(list):
        # temp 없을 때(빈 리스트), 새로운 node를 생성하고 result에 담는다.
        if not temp:
            temp = ListNode(val)
            head = temp
        # temp 있을 때, 현재 node의 다음 node에 새로운 node를 생성하고
        # 현재 node와 연결해준다.
        else:
            temp.next = ListNode(val)
            temp = temp.next

    return head

 

우선 두 연결리스트를 담기 위한 배열 list을 생성해준다. 그리고 while문을 돌리면서 각 연결리스트에서 node를 하나씩 꺼낸 뒤 list에 넣어주면 두 연결리스트가 합쳐진 배열이 완성된다.

 

+

질문이 들어왔어서 추가합니다!

while l1:
    list.append(l1.val)
    l1 = l1.next
while l2:
    list.append(l2.val)
    l2 = l2.next

while문에 l1 노드가 있으면 지금 노드의 value를 list에 append하는 부분에서 이해가 조금 어려운 것 같아서 추가 설명을 붙이고 싶다.

질문 해주셨던 부분이, l1이 [1, 2, 4]인 리스트일 때, 리스트인 l1의 value를 append 해주는건 l1이라는 리스트를 통째로 list 변수 안에 집어넣주는게 아니냐. 라는 건데 이건 연결 리스트의 흐름을 파악하면 어렵지 않게 이해할 수 있다.

 

우선, l1은 [1, 2, 4]인 리스트가 아니라 현재 가리키고 있는 pointer라고 생각해야한다. 그냥 리스트가 아니라 연결리스트이기 때문이다.

append 다음 코드를 보면 l1노드를 l1.next로 옮겨주고 있는데, 이 코드로 노드가 하나씩 다음으로 이동하고 있다는 걸 알 수 있다.

 

while문이 쭉 돌다가 l1 노드의 다음 노드가 존재하지 않는 순간이 오는데, 우리가 Node 객체를 생성해서 맨 뒤에 추가할 때 Node(val, None)으로 next에 None을 담아주고, while문 내부에서 l1을 계속 l1.next로 이동시켜주고 있으니까 연결리스트의 끝부분에 다다르면 l1이 None을 반환하는 순간이 온다. 

 

이해가 됐으면 좋겠다.

 

 

 

연결리스트를 만들기 위한 노드인 temp와 정렬된 노드를 담기위한 연결리스트 head를 생성해주고, for문 자체에서 list를 sorted함수로 정렬한 뒤, 각 데이터를 뽑아준다.

 

현재 가리키고 있는 temp 노드가 비어있을 때, 값을 넣어주기 위해 조건문으로 새로운 노드 temp를 head에 담아주고,

그 다음부터는 배열에서 하나씩 데이터를 꺼내 head에 넣어주면 완성!

 

놀라운게 리트코드에 코드를 넣었을 때, 해설에 나온 코드보다 실행속도가 빠른 걸 확인할 수 있었다. 

하지만 내가 문제를 푸는 목적은 공부이므로 해설 코드도 확인해보자.

 

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    if (not l1) or (l2 and (l1.val > l2.val)):
        l1, l2 = l2, l1 # 다중할당
    if l1:
        l1.next = self.mergeTowLists(l1.next, l2)
    return l1

해설에서는 재귀 구조와 스왑 사용한다. 재귀는 스프링으로 개발을 할 때 순환참조와 관련된 내용으로 봤던 용어인데, 함수가 자기 자신을 호출하는 방식을 재귀 구조, 재귀 호출이라고 부른다! 스왑은 두 변수를 서로 바꾸는 것으로 어렵지 않다.

 

해설의 코드 자체는 간결하지만 재귀 호출을 직접 코드로 확인하는 건 처음이라 정말 헷갈려서 수십번 그림으로 그려봤는데 이해하기 어렵더라... 자, 그림으로 확인해보자!

 

<스압주의!>

첫번째 반복문이다. 

if (not l1) or (l2 and (l1.val > l2.val)):

조건문을 만족하지 않으니 다음 조건문으로 넘어간다. 

 

if l1:
    l1.next = self.mergeTowLists(l1.next, l2)

다음 조건문을 만족하므로 재귀 호출을 한다! l1.next와 l2를 인자로 넘겨주는 다음 함수로 넘어가자.

 

다음 함수로 들어왔다. l1.next를 인자로 받았기 때문에 첫번째 과정에서 사용한 l1인자는 첫번째 반복문에 남아있다.

이번에는 첫번째 조건문을 만족하므로 두 리스트를 스왑한다.

 

두번째 조건문도 만족하니 다시 같은 과정을 반복한다. 아래의 그림들을 쭉 살펴보면 계속 같은 과정을 반복하고 있다.

 

최종적으로 list1이 비어있기 때문에 list1.next와 list2를 스왑하고,

최종 리스트를 return하면 해결!

 

---

마치며

재귀 호출이 코드만 보면 간단해보이지만 그 개념을 이해하기가 정말 어렵다. 이 녀석 덕분에 노트를 거의 5페이지를 가득 채웠다. 그래도 이렇게 오래 고민해보니 앞으로는 덜 헷갈릴 듯 싶어서 뿌듯하다.