23.Merge k Sorted Lists

문제링크: https://leetcode.com/problems/merge-k-sorted-lists/

주어진 오름차순 정렬된 연결 리스트들을 합해 하나의 오름차순 연결 리스트로 만드는 문제다.

Solution

Iterate merging sorted list

병합 정렬과 비슷한 방법으로 병합해 새 연결 리스트를 만드는 것을 반복한다.

Algorithm

• 두 연결 리스트를 병합하기 위해 새 더미 노드를 만든다.
• 두 개의 연결 리스트의 포인터를 통해 값을 비교하고 작은 값을 더미 노드에 이어 붙인다.
• 위 방법을 통해 첫번째 연결리스트에 새 리스트들을 반복해서 병합한다.

var mergeKLists = function(lists) {
    // merge sort의 방식 (앞에서 부터 작은 수를 병합)
    const mergeTwoLists = (a, b) => {
        const dummy = new ListNode(0);
        let cur = dummy;
        while (a && b) {
            if (a.val <= b.val) {
                cur.next = a;
                cur = a;
                a = a.next;
            } else {
                cur.next = b;
                cur = b;
                b = b.next;
            }
        }
        if (a) cur.next = a;
        if (b) cur.next = b;
        return dummy.next;
    }
    
    if (lists.length === 0) return null;
    
    // result에 새 list 병합
    let result = lists[0];
    for (let list of lists.slice(1)) {
        result = mergeTwoLists(result, list);
    }
    return result;
    
};

Iterate with priority queue

기존과 병합하는 과정은 똑같지만 병합하는 list의 방법을 조절한다. Queue를 통해 이미 병합된 list의 우선순위를 뒤로 미뤄 긴 작업을 반복하는 것을 최적화 한다.

Algorithm

• 위와 같은 방법으로 연결 리스트를 병합하는 함수를 이용한다.
• lists를 큐의 형태로 사용한다.
• 앞의 두 원소를 병합하고 병합한 새 리스트는 lists의 가장 맨 뒤로 넣어 우선순위를 미룬다.
• 가장 긴 리스트를 항상 연산에 사용하면 길이만큼 효율성이 떨어지지만 병합된 리스트의 우선순위를 뒤로 미뤄 효율성을 증대시킨다.

var mergeKLists = function(lists) {
    // 두 연결 리스트를 병합하는 함수
    const mergeTwoLists = (a, b) => {
        //  ... 위와 같음
    }
    
    if (lists.length === 0) return null;
    
    // lists as queue (병합된 리스트는 뒤로 추가해서 긴 리스트는 나중에 병합)
    while (lists.length > 1) {
        const a = lists.shift();
        const b = lists.shift();
        const mergedAB = mergeTwoLists(a, b);
        lists.push(mergedAB);
    }
    return lists[0];
    
};