[LeetCode] 21. Merge Two Sorted List 두 정렬 리스트 병합

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

21번 Merge Two Sorted List 는 연결 리스트를 뒤집는 문제이다.

Example

위 문제는 혼자 풀려고 해보았지만, 푸는 도중에 꼬이고 어떤식으로 풀어야할지 전혀 감이 잡히지 않아 책 풀이를 참고하였다.

이 문제는 책 풀이를 보아도 쉽게 이해가 되지 않아서 이해하는데 꽤 걸렸다.

 

# 풀이방법 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[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

| 아이디어  | 

l1과 l2를 비교해 작은 값을 왼쪽으로 오게하고, next는 다음 값으로 재귀호출한다.

 

 

| 핵심 |

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

 

# 결과