[LeetCode] Merge K Sorted Lists

url: https://leetcode.com/problems/merge-k-sorted-lists

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

k개의 정렬된 링크드 리스트를 합치는 문제. 물론 정렬된 상태의 한개의 리스트로.

다양한 방법이 나올 수 있지만, 가장 처음 생각한 것은 재귀적 방법이다. 두 개의 리스트를 합치는 방법이야 알고 있으니 (리스트 두개를 선회하며 크기 비교를 하며 하나로 합치는 방법) 마치 merge sort처럼, 계속해서 쪼개다가 두 개의 비교대상이 있으면 그것만 합치는 방법.

하지만 머지소트가 개인적으로는 시간이 오래걸리고, 어차피 자바로 짜기 때문에 쉬운 방법이 우선순위큐 (PriorityQueue)라는 생각을 했다. 전체 길이를 알아내고, 그 길이만큼 그냥 우선순위 큐에 넣고 한번에 poll하는 방식.

사실 속도는 Merge Sort에 조금은 못미치지만, 개념적으로 보면 O(nlogn)의 시간복잡도는 같으니깐, 굳이 재귀를 쓰지 않는 PriorityQueue 에 한표를 던지고 싶다. 물론 재귀야 잘하면 좋지만 자칫 잘못하면 stack overflow니깐 개인적으로는 피함..

 /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode rslt = new ListNode(0);
        int[] n = new int[lists.length];
        int k = 0, n2 = 0;
        
        if(lists.length == 0)   return null;
        
        for(ListNode l : lists){
            ListNode t = l;
            while(t != null){
                n[k]++;
                n2++;
                t = t.next;
            }
            k++;
        }
        
        if(n2 == 0) return null;
        
        
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(n2, new Comparator<Integer> () {
            @Override
            public int compare(Integer e1, Integer e2){
                return (Integer) (e1 - e2);
            }
        });
        
        for(ListNode l : lists){
            ListNode t = l;
            while(t != null){
                queue.add(t.val);
                t = t.next;
            }
        }
        
        ListNode temp = rslt;
        
        while(queue.peek() != null){
            int v = queue.poll();
            temp.next = new ListNode(v);
            temp = temp.next;   
        }
        
        return rslt.next;
        
    }
}
 
아 참고로 Integer의 경우 굳이 Comparator를 생성하지 않아도 된다. @Override된 부분 제외하면 조금 더 빠르다.