[LeetCode] 23. Merge k Sorted Lists

문제(23. Merge k Sorted Lists)

linked list들이 들어있는 k배열이 있다. 그리고 각각의 linked list는 오름차순으로 정렬되어 있다. 배열 k에 있는 linked list들을 합쳐 오름차순으로 정렬한 linked list를 리턴하라.

문제에 대한 나의 생각

접근 하는 방법에 따라 이 문제의 난이도가 천차만별이라 생각한다.
만약 모든 linked list들을 한개씩 비교하는 방식으로 접근하면 처음 설계할 때 매우 중요하다고 생각한다. 그래서 이러한 방식은 다음에 시도하기로 하고 다른 방법으로 접근했다.

아이디어

linked list의 값을 저장할 새로운 배열을 생성한다. 그리고 linked list들의 값을 모두 새로 생성한 배열에 저장한다. 그리고 sort()를 사용하여 정렬한다. 이 후 새로운 linked list를 생성하고 정렬한 배열의 값들을 새로운 linked list에 차례대로 저장한다. 마지막에 리턴 값은 새로운 linked list의 next로 바라보게 한다.

---

코드

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ans_arr = []
        for node in lists:
            while node is not None:
                ans_arr.append(node.val)
                node = node.next
        ans_arr.sort()
        ans_node = ans = ListNode()
        for i in ans_arr:
            ans.next = ListNode(i)
            ans = ans.next
        # 첫번째 값이 next에 저장되어 있기 때문에 next로 시작
        return ans_node.next