[LeetCode] #21. Merge Two Sorted Lists (python)

문제

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

Merge Two Sorted Lists - LeetCode

주어진 두 연결 리스트를 하나의 정렬된 연결 리스트로 반환해야 한다.

 

예시 입출력

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

 

 

풀이

 

책 풀이

재귀 구조

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

조건문에서 괄호가 없어도 우리가 원하는 순서로 실행된다. 비교연산이 1순위로 실행되고 and가 or보다 먼저 실행되기 때문이다.

만약 list1보다 list2가 작으면 둘의 위치를 바꿔주기 때문에 l2가 l1의 현재 값에 이어서 연결된다.

list1=[1,2,4] list2=[1,3,4] 일때 둘의 변화를 살펴보자

list1 : 1→1→3→4 | list2 : 2→4

list1 : 1→1→2→4 | list2 : 3→4

list1 : 1→1→2→3→4 | list2 : 4

list1: 1→1→2→3→4→4

 

 

참고한 책 : 파이썬 알고리즘 인터뷰