[리트코드/leetcode/python] 21. Merge Two Sorted Lists

이미지를 누르면 문제 링크를 보실 수 있습니다.

위 문제는 정렬된 두 리스트를 병합하는 문제입니다.

단순 알고리즘 문제를 푸는 것이 아니라 자료구조를 고려해서 풀어야 하는 문제였는데요, 자료구조의 필요성이 느껴진 문제이기도 했습니다.

 

문제를 접근하는 방식에는 2가지 방법이 있는데요,

하나는 재귀적 알고리즘을 사용하는 방법과 두번째로는 더미노드를 만들어 그 뒤에 이어 붙이는 방법이었습니다.

시간 복잡도는 둘다 O(n+m)이 나오는데요, 두 번째 방법으로 푼 코드를 살펴봅시다.

# 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]:
        
        dummy = ListNode()
        tail = dummy
        
        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
        
        if list1:
            tail.next = list1
        if list2:
            tail.next = list2

        return dummy.next

먼저, dummy 노드를 선언해줍니다.

디폴트 인자값을 가지는 ListNode() 객체를 선언해주고, 해당 dummy 객체를 tail에 할당해줍니다. 우리는 이 tail을 갱신해나가면서 살펴볼거에요.

 

당연히 list1과 list2가 None이 아니어야 비교가 가능하므로, while 조건문에 list1과 list2가 빈 값이 아닐 때 순회하도록 설정해줍니다.

list1.val 이 list2.val 보다 작다면, tail의 다음 노드는 list1이 되고, 기존 list1도 다음 노드를 가리키도록 갱신해줍니다.

마찬가지로, list2.val이 list1보다 작거나 같다면, tail의 다음 노드는 list2가 되고, list2는 기존 list2의 다음 노드로 갱신됩니다.

그리고 tail도 tail의 다음노드로 갱신해줘야 이어서 붙이겠죠? ( tail = tail.next )

 

while문을 안 타거나 빠져나올 때도 처리해줘야 합니다.

list1이 빈값이 아니라면, tail.next 는 list1이 되겠고

list2가 빈값이 아니라면, tail.next는 list2가 됩니다.

 

마지막으로는 기존에 초기화한 dummy의 next 를 반환해야 합니다.

위 예시1번에서 dummy를 출력해보면, 아래와 같이 나오기 때문이에요. 

ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: None}}}}}}}

기존 val : 0을 가지는 dummy의 next부터 시작하니까 우리는 dummy의 next를 뽑아줘야 하는 셈입니다.

 

이 외에도 재귀적으로 푸는 코드는 아래와 같습니다.

# 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 or list2 is None:
            return list1 or list2
        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.val 이 list2.val 보다 작다면, list1.next와 list2를 또 비교하면 되고,

list2.val 이 list1.val 보다 작거나 같으면, list2.next와 list1을 비교하면서, 

작은 수 순서대로 노드가 연결될 수 있도록 하면 되는 셈입니다.

재귀적으로 함수를 타니까 기준이 된 list를 그대로 반환해주면 됩니다.

 

이상 Merge Two Sorted Lists 문제를 정리해봤습니다.

 

함께 보면 좋은 영상을 첨부할게요!

https://www.youtube.com/watch?v=XIdigk956u0

https://www.youtube.com/watch?v=VTjtSFdMj3s