[LeetCode] 21. Merge Two Sorted Lists

# 문제 설명
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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.

 

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]

 

이 문제를 보고 생각했던 방식은 각 리스트를 순회하는 두 개의 reference가 있고, 각 노드의 값을 비교하여 작은 값에 해당하는 것을 새로운 노드의 값으로 추가하는 방식을 생각하였다. 따라서 처음에는 더미 노드를 하나 생성하고 그 뒤로 next를 붙여가는 방식을 이용하였다.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        node = ListNode()
        ref_node = node
        while list1 is not None and list2 is not None:
            if list1.val < list2.val:
                node.next = ListNode(list1.val)
                list1 = list1.next
            else:
                node.next = ListNode(list2.val)
                list2 = list2.next
            node = node.next
        node.next = list2 if list1 is None else list1
        return ref_node.next

 

이를 방식은 동일하나 recursive를 이용하는 방법도 있다.

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

 

아직 그래프 문제만 보면 쉬운 문제임에도 불구하고 어려움을 느끼는 것 같다.