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

정렬되어 있는 두 연결 리스트를 합쳐라.

 

 

Input: l1 = [1,2,4], l2 = [1,3,4]

Output: [1,1,2,3,4,4]

 

 

예시

 

 

 

 

 

 

** 깔끔한 답안 **

 

 

 

 

1. 재귀 구조로 연결

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    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.mergeTwoLists(l1.next,l2)
        return l1

 

해설:

 

우선 Input으로 주어진 두 연결 리스트가 정렬되었다는 것이 중요하다.

병합 정렬에서 마지막 조합 시 첫 번째 값부터 차례대로만 비교하면 한 번에 해결되듯이,

이 또한 첫 번째부터 비교하면서 리턴하면 쉽게(?) 풀 수 있는 문제다.

 

코드 자체만 보고는 이해하기 힘든데

(사실 아직도 100% 이해했다고 말하긴 힘들다)

일단 핵심은

l1이 최종 리턴 값이라 생각하면

l1이 l2보다 클 때

l1, l2 = l2, l1을 해줘서

l1에 차곡차곡 값을 정렬시켜 주는 거다!

 

백번 글 쓰여있는 걸 읽는 것보다

일단 손으로 연결 리스트를 그려가며 이해하는 것이 중요하다.

 

 

 

 

 

 

 

출처: 파이썬 알고리즘 인터뷰(박상길 지음, 정진호 일러스트) 출판사 [책만]