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.

제한사항

• k == lists.length
• 0 <= k <= $10^4$
• 0 <= lists[i].length <= 500
• $-10^4$ <= lists[i][j] <= $10^4$
• lists[i] is sorted in ascending order.`
• The sum of lists[i].length won't exceed $10^4$.

접근1

정렬된 ListNode들이 주어졌을 때 이를 합친 정렬된 노드를 반환하는 문제였습니다.

병합 정렬의 Merge 응용문제구나! 하고 list 내 요소를 접근해서 가장 작은 것을 정답에 추가하는 방식으로 전개를 해서 풀었습니다.

답안

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length <= 0)
            return null;

        ListNode ret = null, lastNode = null;
        ListNode ret2 = null;
        while(true){
            int minValue = Integer.MAX_VALUE;
            int minNodeIndex = 0;
            boolean isEmpty = true;
            for(int i = 0; i < lists.length; ++i){
                if(lists[i] == null)
                    continue;
                
                int value = lists[i].val;
                if(minValue > value) {
                    minValue = value;
                    minNodeIndex = i;
                    isEmpty = false;
                }
            }

            if(isEmpty)
                break;   
            
            // If it's first time
            if(null == ret){
                ret = new ListNode();
                ret2 = ret;
            }

            ret.val = minValue;
            ret.next = new ListNode();
            lastNode = ret;
            ret = ret.next;

            lists[minNodeIndex] = lists[minNodeIndex].next;
        }
        
        if(null != lastNode)
            lastNode.next = null;
        
        return ret2;
    }
}

접근2

정답은 냈지만, 속도가 느려 이번에도 상위 랭킹의 답안을 보았어요.

그리고 해당 로직을 병합 정렬Merge Sort처럼 분할 정복Divide-and-conquer해서 Merge하는 것을 발견했습니다!

매번 lists 요소들을 순회 접근해서 비교해 $O(n^2)$인 제 풀이와 달린 이 풀이는 $O(nlogn)$의 속도를 보이는 것이었죠!

병합 정렬Merge Sort을 하드코딩이 가능할 때까지 연습했는데 응용까지 못했던 점에 대해 반성하게 됩니다...

답안

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeLists(lists, 0, lists.length - 1);
    }
    ListNode mergeLists(ListNode[] lists, int lo, int hi) {
        if (lo == hi) {
            return lists[lo];
        }
        int mid = lo + (hi - lo) / 2;
        ListNode l = mergeLists(lists, lo, mid);
        ListNode r = mergeLists(lists, mid + 1, hi);
        return merge(l, r);
    }
    
    ListNode merge(ListNode l, ListNode r) {
        ListNode dumb = new ListNode(-1);
        ListNode p = dumb;
        while (l != null && r != null) {
            if (l.val < r.val) {
                p.next = l;
                l = l.next;
            } else {
                p.next = r;
                r = r.next;
            }
            p = p.next;
        }
        if (l == null) {
            p.next = r;
        } else {
            p.next = l;
        }
        return dumb.next;
    }
}