[코테] 리트코드 연결 리스트 21. Merge Two Sorted Lists

21. Merge Two Sorted Lists

문제 링크

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

문제 설명

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.

제한 사항

• 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.

입출력 예 #1

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

입출력 예 #2

1. Input: list1 = [], list2 = []
2. Output: []

입출력 예 #3

1. Input: list1 = [], list2 = [0]
2. Output: [0]

문제 풀이

재귀 구조를 이용한 뒤집기 기법으로 풀이 가능하다.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if (not list1) or (list2 and list1.val > list2.val):
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1