Week 1-2. [Linked List] 21. Merge Two Sorted Lists (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Merge Two Sorted Lists - LeetCode

두 개의 링크드 리스트가 주어질 때, 이를 오름차순으로 Merge 하라.

• 각각의 링크드 리스트는 오름차순 정렬되어 있다.

 

🔎 어떤 식으로 접근했는가?

list1과 list2 각각이 이미 오름차순 정렬 되어있기 때문에, 둘을 비교하여 더 큰 값을 채택한다.  

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

두 개의 링크드 리스트의 최대 길이가 50이므로 linear search를 이용할 것이다.

 

📝 의사 코드

 

🎯 구현 코드

우선 아래 코드는 테스트 케이스를 통과하지 못한다.

연결 리스트 [1,2,3]과 [1,3,4]를 병합했을 때 [1,1,2,3,4,4]가 나와야 하는데, [4,4,3,2,1,1]이 나온다.

# 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 == None and list2 == None: return None
        elif list1 == None: return list2
        elif list2 == None: return list1

        h1 = list1
        h2 = list2

        # initial
        head = None
        linked_lst = None
        if h1.val >= h2.val:
            head = ListNode(h2.val)
            h2 = h2.next
        else:
            head = ListNode(h1.val)
            h1 = h1.next
        linked_lst = head

        # 이어붙이기
        while h1 != None and h2 != None :
            if h1.val >= h2.val:
                cur = ListNode(h2.val, linked_lst)
                h2 = h2.next
            else:
                cur = ListNode(h1.val, linked_lst)
                h1 = h1.next
            linked_lst = cur


        # 남은 것 이어붙이기
        while h1 != None:
            cur = ListNode(h1.val, linked_lst)
            linked_lst = cur
            h1 = h1.next
        while h2 != None:
            cur = ListNode(h2.val, linked_lst)
            linked_lst = cur
            h2 = h2.next

        return linked_lst

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

주어진 링크드 리스트를 하나씩 순회하므로 O(N)의 시간 복잡도를 갖는다.

 

✍️ 성능 회고

성능은 나쁘지 않지만 의도와 다르게 동작한다.

그리고 코드가 복잡하다.

 

💡 무엇을/어떻게 개선할 수 있을까?

cur = ListNode(h2.val, linked_lst) 에서 h2.val을 기존 linked_lst 뒤에 붙여서 오름차순이 아닌 내림차순 정렬이 되는 것 같다.

이를 개선해보자.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

# 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]:

        head = ListNode(-1) # dummy node # 실제 연결리스트의 시작 부분은 head.next에 위치한다
        cur = head # 현재 생성중인 새로운 연결 리스트의 마지막 논드를 가리킨다.

        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next # 다음 노드로 업데이트

        # 마지막 노드
        if list1 != None: cur.next = list1
        else: cur.next = list2

        return head.next

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

O(N)의 시간 복잡도를 갖는다.

 

느낀 점

링크드 리스트를 직접 구현하는 연습을 많이 해봐야할 것 같다. 아직 낯설고 부족함을 느꼈다.

 

참고 자료

[Python 으로 푸는 Leetcode]21. Merge Two Sorted Lists