[Problem List - Array / String] 21. Merge Two Sorted Lists

[Q] [Easy]

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.

 

 

• list 2개 합쳐서 sort 하면 될 것으로 생각했는데, "linked" 가 복병이었음
• list1 과 list2 가 모두 none 인 경우, 하나만 none 인 경우는 따로 처리해줌
• list1 과 list2 크기 비교하여 처리 해주는건 재귀적으로 처리함

 

# Answer

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None and list2 is None :
            return None

        elif list1 is None or list2 is None :
            return list1 or list2

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