[PS] Leet | 23. 정렬된 K개의 리스트 합치기

문제

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

예시

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

조건

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

답

여러 개의 리스트 중에서 두 개 씩 선택해 합치는 분할 정복을 사용합니다.

 

위 과정을 계속 반복하면 lists에는 하나의 리스트만 남게 되고, 그것이 최종 결과물이 됩니다.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
const mergeTwoLists = (list1, list2) => {
    let node = new ListNode(0, null);
    const head = node;

    while(list1 && list2) {
        if (list1?.val <= list2?.val) {
            node.next = list1;
            node = node.next;
            list1 = list1?.next;
        } else {
            node.next = list2;
            node = node.next;
            list2 = list2?.next;
        }
    }

    if (!list1) node.next = list2;
    if (!list2) node.next = list1;
    return head.next;
};

var mergeKLists = function(lists) {
    if (lists.length == 0) return null;

    while (lists.length > 1) {
        const listsMerged = [];

        for (let i=0; i<lists.length; i+=2) {
            const l1 = lists[i];
            const l2 = i+1 < lists.length? lists[i+1] : null;
            listsMerged.push(mergeTwoLists(l1, l2));
        }
        lists = listsMerged;
    }

    return lists[0];
};

총 node의 개수 N, 리스트의 개수 K일 때

 

시간 복잡도 : O(NlogK)

공간 복잡도 : O(1)