[LeetCode | Python] 21. Merge Two Sorted Lists

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.

두 개의 링크드리스트를 하나의 sorted linked list로 만들기!

 

풀이1: Recursion (재귀)

# 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]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

list1과 list2의 현재 값을 비교한다.

더 작은 값을 가진 노드가 결과 리스트의 헤드가 되고, 그 노드의 next를 재귀 호출로 이어간다.

list1이나 list2가 끝까지 가면 남은 리스트를 그대로 붙인다.

 

두 리스트의 모든 노드를 방문하므로 시간 복잡도는 O(n+m)

재귀 호출이 깊어질수록 콜 스택에 추가되므로 리스트 길이 만큼의 공간을 사용하기 때문에 공간 복잡도는 O(n+m)

 

 

풀이2: Iteration (반복)

# 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: ListNode, list2: ListNode) -> ListNode:
        dummy = node = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next
            node = node.next

        node.next = list1 or list2

        return dummy.next

dummy라는 가짜 헤드 노드를 사용해 결과 리스트를 만든다.

두 리스트의 노드를 비교해 더 작은 값을 결과 리스트에 붙이고 포인터를 이동시킨다.

한쪽 리스트가 끝나면 남은 노드를 결과 리스트에 바로 붙인다.

 

두 리스트의 모든 노드를 방문하므로 시간 복잡도는 O(n+m)

더미 노드와 몇 개의 포인터만 필요하므로 추가 메모리를 거의 사용하지 않아, 공간 복잡도는 O(1)이다.