[Leetcode]21. Merge Two Sorted Lists

1. 문제 

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.

 

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]
 

Constraints:

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.

 

 

2. 풀이 

첫 번째 방법은 뱀이 작은 수를 하나씩 먹어가며 두 개의 linked list를 탐색하는 방법이다. 일명, merged linked list 그 자체다. 

이 방법은 dummy_node를 만들어, 그 뒤에 붙여가면서 반복을한다. 내가 작성한 풀이는 한번 더 꼬아서 작성을 했다. 그래서, 불필요한 코드들이 많다. 0이라는 dummy_node를 만든 후, 그냥 반복하면 되는 건데, 이 생각을 왜 못했나 모르겠다. 

따라서, 다른사람의 solution을 여기에 복붙 하겠다. 

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy

        while list1 and list2:
            if list1.val > list2.val:
                cur.next = list2
                list2 = list2.next
            else:
                cur.next = list1
                list1 = list1.next
            
            cur = cur.next
        
        if list1:
            cur.next = list1
        else:
            cur.next = list2
        
        return dummy.next

만약에 list1과 list2 둘중에 하나라도 None이 나온다면 하나의 list는 이미 다 뱀한테 잡아먹혔다는 이야기가 된다. 따라서, 반복문을 끝내고, 남아있는 list들의 element들을 current_node 뒤에 붙여주기만 하면 된다. 

 

두 번째 방법은 recursion을 이용하는 거다. 재귀함수가 너무 어려워, 어떻게든 구현해보고자 했지만, 실패하고, solution을 봤다. 이 solution작성자는 list1을 더 작은 값에 할당시키고, list2를 더 큰 값에 할당시켜, 결과적으로 return list1을 해준다. 이렇게 되면, list1.next = 작은 값이 되므로, 상당히 매력적인 풀이가 된다. 

 

내가 왜 이렇게 풀지못했을까? recursion에 대한 경험부족이다. 

따라서, 다음번에 만났을때는 1. work flow를 작성한다. 즉, 큰 뼈대를 먼저 그린다. 2. return값을 정한다. 3. base case를 설정한다. 이런 3가지 원칙으로 문제를 풀어야겠다는 생각을 했다. 

 

recursion을 다룰때, 버려야 할 습관중하나는 꼬리에 꼬리를 물고 함수를 끝까지 해석하는 것이다. 그냥 1번과 2번을 잘 작성했다면 큰 문제가 없지 않겠는가? 3번을 검사할 때만 보도록 하자.

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: 
        if list1 is None or list2 is None:
            return list1 if list1 else list2

        if list1.val > list2.val:
            list1, list2 = list2, list1 
        list1.next = self.mergeTwoLists(list1.next, list2)
        return list1