[Leetcode] 21. Merge Two Sorted Lists_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '21. Merge Two Sorted Lists'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Merge Two Sorted Lists' 알고리즘 문제

 

STEP 2. 'Merge Two Sorted Lists' 코드(code)

 

STEP 3. 'Merge Two Sorted Lists' 해설

 

STEP 4. 'Merge Two Sorted Lists' solution

 

반응형

 

STEP 1. '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.

 

정렬된 두 개의 리스트 list1과 list2의 값이 제공됩니다.
한 정렬된 리스트에서 두 리스트를 병합합니다. 병합된 리스트는 처음 두 리스트의 노드를 서로 연결하여 만들어야 합니다.
병합된 리스트의 값을 반환합니다.

 

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.

---

STEP 2. 'Merge Two Sorted Lists' 코드(code)

 

■ Runtime: 48 ms, faster than 58.21% of Python3 online submissions for Merge Two Sorted Lists.
■ Memory Usage: 13.9 MB, less than 78.59% of Python3 online submissions for Merge Two Sorted Lists.

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 2개 리스트가 None일 경우
        if not list1 and not list2:
            return None
        
        # 2개 리스트 중 하나만 None일 경우
        elif not list1 or not list2:
            return list1 or list2
        
        # 2개 리스트 모두 None이 아닌 경우
        else: 
            tail = dummy = ListNode()
            
            while list1 and list2:
                if list1.val < list2.val:
                    tail.next = list1
                    list1 = list1.next
                else:
                    tail.next = list2
                    list2 = list2.next
                tail = tail.next
            tail.next = list1 or list2

        return dummy.next

---

STEP 3. 'Merge Two Sorted Lists' 해설

 

copy를 사용할 수 없으며, 주어진 리스트를 활용해서 작성해야 되는 경우입니다. 2개의 리스트에서 (1) All None, (2) One of None, (3) Not None으로 3가지 경우로 나눠서 코드를 작성했습니다.

 

(1) All none: 빈 리스트 반환

(2) One of None: 값이 있는 리스트 반환

(3) Not None: 각 리스트 간의 값을 비교해서, 이 중 작은 값을 새롭게 생성한 dummy에 더하는 방식으로 연산했습니다. 그리고 대소 비교 이후에 남은 값을 dummy에 더해서, 최종적으로 이를 반환하는 방식입니다.

 

 

STEP 4. 'Merge Two Sorted Lists' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

이 중에서 속도, 데이터 점유율이 가장 우선한 결과를 정리했습니다.

 

■ Runtime: 37 ms, faster than 90.13% of Python3 online submissions for Merge Two Sorted Lists.
■ Memory Usage: 13.9 MB, less than 78.59% of Python3 online submissions for Merge Two Sorted Lists.

 

# iteratively
def mergeTwoLists1(self, l1, l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next
    
# recursively    
def mergeTwoLists2(self, l1, l2):
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2
        
# in-place, iteratively        
def mergeTwoLists(self, l1, l2):
    if None in (l1, l2):
        return l1 or l2
    dummy = cur = ListNode(0)
    dummy.next = l1
    while l1 and l2:
        if l1.val < l2.val:
            l1 = l1.next
        else:
            nxt = cur.next
            cur.next = l2
            tmp = l2.next
            l2.next = nxt
            l2 = tmp
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '21. Merge Two Sorted Lists'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.