[리트코드 (LeetCode)] Merge Two Sorted Lists: Linked List (Python)

Merge Two Sorted List

• https://leetcode.com/explore/featured/card/top-interview-questions-easy/93/linked-list/771/
• 분류: Top Interview Questions - Easy - Linked List

Explore - LeetCode

문제

• 두 개의 정렬된 연결 리스트 list1과 list2가 있다. 이를 하나의 정렬된 연결 리스트로 합치시고 head를 반환하시오.
• type list1: Optional[ListNode], type list2: Optional[ListNode] / rtype: Optional[ListNode]

예시

조건

• 노드의 수는 두 리스트 모두 0~50
• 노드의 value는 -100~100두 리스트 모두 non-decreasing order로 정렬되어 있음

풀이

1. 투 포인터, 더미 노드 활용

(1) 새 노드(연결 리스트)를 만들고 (start) 그 리스트의 head를 기억하기 위해 dummy 노드 생성

(2) 두 포인터(각 리스트의 헤드를 가리킴)가 가리키는 값 중 더 작은 값을 새 리스트가 가리키게 하고 새 리스트와 값을 넣은 리스트의 포인터를 하나씩 증가시킴

(3) 둘 중 한 리스트의 끝에 도달할 때까지 반복한 후 남은 리스트를 맨 끝에 추가 (dealLast)

→ 연결 리스트이므로 일일이 노드를 추가할 필요 없음(뒤에서 설명)

(4) 새로 만든 연결 리스트의 헤드 반환

class Solution(object):
    def mergeTwoLists(self, list1, list2):        
        start = ListNode()
        dummy = start
        
        while list1 and list2:
            if list1.val < list2.val:
                start.next = list1
                list1 = list1.next
            else:
                start.next = list2
                list2 = list2.next
            start = start.next
            
        self.dealLast(start, list1)
        self.dealLast(start, list2)
        return dummy.next    
        
    def dealLast(self, start, list_):
        while list_:
            start.next = list_
            list_ = list_.next
            start = start.next

Time: O(n) / Space: O(1)

Runtime: 20 ms (beats 83.12%) / Memory Usage: 13.6 MB (beats 12.77%)

 

그런데 이렇게 풀고 나니 이 문제는 연결 리스트니까 리스트를 합쳤을 때와 다르게 맨 마지막에 남은 노드를 일일이 연결해줄 필요 없이 남은 연결 리스트의 헤드를 가리키는 것으로 끝난다는 사실을 깨달았다. 굳이 while을 돌릴 이유가 없는 것이다. 이렇게 수정한 코드는 다음과 같다.

• 출처: https://leetcode.com/explore/featured/card/top-interview-questions-easy/93/linked-list/771/discuss/1826693/Python3-MERGING-Explained

class Solution:
    def mergeTwoLists(self, list1, list2)
        cur = dummy = ListNode()
        while list1 and list2:               
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1
            else:
                cur.next = list2
                list2, cur = list2.next, list2
                
        if list1 or list2:
            cur.next = list1 if list1 else list2
            
        return dummy.next

Runtime: 22 ms (beats 69.99%) / Memory Usage: 13.6 MB (beats 36.02%)

 

이 방법의 공간 복잡도가 O(1)인 이유는 맨 처음에 더미 노드와 sorted list 트래킹용 노드 2개를 만든 것 외에는 새로 노드를 생성하지 않고 기존 연결 리스트에 있는 노드의 연결만 바꾸어 주었기 때문이다. cur 노드는 정렬되지 않은 남아있는 노드들 중 가장 작은 노드를 트래킹하여 연결을 바꿔준다(정렬한다).

---

참고로 미리 두 리스트가 None인지 확인해 리턴하는 코드를 앞에 추가했을 때 실행 속도는 느려지고 메모리 사용량은 줄었다. (Runtime: 27 ms / Memory Usage: 13.55 MB)

맨 마지막 dealLast를 함수화하지 않고 그냥 2개의 while loop로 적었을 때도 실행 속도는 느렸고 메모리 사용량은 줄었다. (Runtime: 32 ms / Memory Usage: 13.5 MB)

두 처리를 하지 않았을 때 속도는 빨라지고 메모리 사용량은 늘었다는 이야기다.

if list1 == None:
	return list2
elif list2 == None:
	return list1
elif list1 == None and list2 == None:
	return None

 

2. 재귀적 풀이

둘 중 더 작은 노드를 가진 연결 리스트의 뒤에 남은 sorting 결과를 붙이는 방법

• 출처: https://leetcode.com/explore/featured/card/top-interview-questions-easy/93/linked-list/771/discuss/9735/Python-solutions-(iteratively-recursively-iteratively-in-place).

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

Time: O(n) / Space: O(1)

Runtime: 20 ms (beats 83.12%) / Memory Usage: 13.5 MB (beats 36.02%)