23. Merge k Sorted Lists

문제

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

예시

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

풀이

처음 이 문제를 보고 굉장히 간단한 문제인 것 같은데 난이도가 hard 로 되어 있어 의아했다. 하지만 역시는 역시 역시라는 말이 있듯이, 단순한 배열의 문제가 아니었다. 바로 Linked List 라고 불리는 자료구조에 관한 문제였다.

Linked List(링크드 리스트)는 말그대로 '연결'과 관련이 있는 다른 형태의 자료구조이다. array와 list가 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조라면, Linked List는 노드와 노드가 연결을 이용해서 리스트를 구현한 것이다. Linked List의 기본구조는 다음과 같다.

출처 : Linked Lists in Python: An Introduction, Real Python

구조에서 알 수 있듯이, 엘리먼트를 포함하고 있는 노드들은 순차적인 연결이 되어 있다. 노드와 노드의 연결에는 다음 노드를 가르키는 포인터를 담은 구조로 이루어져 있기 때문에 포인터를 활용한 새로운 노드의 삽입 및 삭제가 효율적이라고 할 수 있다. python 기초 - 자료구조편에서 다욱 자세히 다룰 계획이다.

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        data = []
        if len(lists) == 0: return None
            
        if len(lists) == 1: return lists[0]
            
        for lst in lists:
            if lst == None: continue
                
            data.append(lst.val)
            while lst.next: # 노드가 끝날 때까지 탐색
                lst = lst.next
                data.append(lst.val)

        lists = ListNode()
        if len(data) == 0: return None
        data.sort()
        
        for i in range(len(data)):
            if i == 0:
                lists.val = data[i]
            else:
                node = lists
                # node.next가 None 없을 때까지, 더 input할 엘리먼트가 없을 때까지
                while node.next: 
                    node = node.next
                node.next = ListNode(data[i])
                
        return lists

다시 아예 Linked List 에 대한 개념이 없고 이 문제를 접한 상태에서는 다음과 같은 방법으로 문제에 접근했다.

• 여러 개의 Linked List의 node를 탐색하면서 속한 엘리먼트를 저장
• 저장된 엘리먼트를 문제에서 요구했는데 정렬
• 정렬된 엘리먼트의 순서대로 새로운 하나의 Linked List 형성

각 Linked List의 모든 노드를 탐색하기 위해서는 노드의 next를 활용해서 다음 노드가 없을 때까지(None) 탐색하여 엘리먼트를 저장할 수 있었다.

그런데 예외사항이 몇가지 존재했다. 하나는 비어있는 Linked List이고 다른 하나는 하나의 Linked List일 때 이다. 후자의 경우에는 그저 input으로 받은 Linked List를 반환해 주면 되었다. 전자의 경우에는 어떠한 노드도 엘리먼트도 존재하지 않았기 때문에 None 을 반환해 주었다.

새로운 Linked List 를 만들어 줄 때에도, 저장하여 정렬한 엘리먼트들이 더이상 node로 들어가지 않을 때까지 Linked List를 계속 연결해준다.

결과

131 / 131 test cases passed.
Status: Accepted
Runtime: 4052 ms
Memory Usage: 18 MB