[LeetCode]Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/

Merge Two Sorted Lists - LeetCode

 

문제 분석

두개의 리스트를 오름차순으로 정렬하여 하나의 리스트를 만드는 문제입니다.

 

처음 시도한 답안

# r 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]:
        flag1 = False 
        flag2 = False
        output = []

        cur = dummy = ListNode()
        while True:
            if list1 is None:
                flag1 = True
            if list2 is None:
                flag2 = True

            if not flag1 and not flag2:
                if list1.val < list2.val:
                    dummy.next = list1
                    list1 = list1.next
                    dummy = dummy.next
                    continue
                if list1.val == list2.val:
                    dummy.next = list1
                    list1 = list1.next
                    dummy = dummy.next
                    continue
                if list1.val > list2.val:
                    dummy.next = list2
                    list2 = list2.next
                    dummy = dummy.next
                    continue
            
            if flag1 and flag2:
                break

            if flag1:
                dummy.next = list2
                list2 = list2.next
                dummy = dummy.next
                continue
            
            if flag2:
                dummy.next = list1
                list1 = list1.next
                dummy = dummy.next
                continue

        return cur.next

접근 방법

1. list1, list2가 비어있지 않을 때까지 반복합니다.
2. list1, list2 노드가 비어있다면 flag1, flag2를 True로 설정합니다.
3. 두 노드가 모두 비어있지 않을 때, 값의 대소관계를 비교 후 next 노드로 이동시킵니다.
4. 두 노드가 모두 비어있다면 반복문을 탈출합니다.
5. 두 노드중 비어있지 않은 것이 있다면 연결시키고 next 노드로 이동시킵니다.
6. 노드가 이동하는 과정에서는 dummy 노드를 활용해 값들을 연결시켜 줍니다.

이 문제를 해결하는데 가장 중요한 포인트는 cur 와 dummy 노드의 활용방법입니다. dummy 노드는 next 노드로 이동하는 상황에서 값을 연결시켜 줌으로써 cur 노드에서 연결된 값들을 확인할 수 있게 합니다.

 

다만, 첫번째 방법은 실패하는 케이스를 하나씩 커버하면서 작성했기에 가독성이 매우 떨어집니다. 따라서 조금 더 최적화된 방법을 찾아서 적용했습니다.

 

두번째로 시도한 답안

# r 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]:
        cur = dummy = ListNode()
        # 둘 중 하나가 소진될 때 까지 반복
        while list1 and list2:
            if list1.val <= list2.val:
                dummy.next = ListNode(list1.val)
                list1 = list1.next
            else:
                dummy.next = ListNode(list2.val)
                list2 = list2.next
            dummy = dummy.next

        # 남은 요소들이 list1인 경우 마지막에 연결
        if list1:
            dummy.next = list1

        # 남은 요소들이 list2인 경우 마지막에 연결
        if list2:
            dummy.next = list2

        return cur.next

접근 방법

1. list1, list2가 비어있지 않는 동안 반복합니다.
2. list2에 담긴 값이 크거나 같다면, dummy의 next 노드로서 list1 노드를 설정합니다.
3. list1은 다음 노드로 이동합니다.
4. list2에 담긴 값이 작다면, dummy의 next 노드로서 list2 노드를 설정합니다.
5. list2는 다음 노드로 이동합니다.
6. dummy 노드도 next 노드로 이동합니다.
7. 반복이 끝난 후, list1이 남아있다면 맨 뒤에 list1을 연결시켜 줍니다.
8. 반복이 끝난 후, list2가 남아있다면 맨 뒤에 list2를 연결시켜 줍니다.

기본적인 풀이 방법은 첫번째와 같습니다. 첫번째에서 불필요한 코드와 조건들을 제거하여 최적화 한 코드입니다.

 

cur 와 dummy 노드 2개를 활용하는 방법을 떠올리지 못해 어려웠던 문제였습니다. 방법을 알고난 뒤에는 크게 어렵게 느껴지지 않았는데 연습이 필요할 것 같습니다.

또한, 처음에는 output만 확인하고 list에 값을 append 하는 방식으로 구현하려 했으나 주석에 나와있듯이 ListNode 형태로 return 해야 했기에 여러 풀이들을 참고했습니다.