Leet code (Hard): 23. Merge k Sorted Lists - JAVA

 

 

합쳐야할 LinkedList가 두개가 아니다.
여러개의 LinkedList를 전부 돌면서 하나하나 비교를 하는것은 매우 비효율적이고 방식도 복잡할 것이다.

따라서, 
전체 노드를 각각으로 보고 정렬시킨후 연결 시키는 방식으로 풀어내야한다.
정렬을 위해선 PriorityQueue를 사용하는 것이 가장 효율적이다.

Step1) 

가장 먼저 value를 보고 정렬해주는 PriorityQueue를 생성해서,

주어진 각 리스트의 헤드를 삽입한다. 
PriorityQueue에 한번 삽입할때의 시간복잡도는 O(log K)이다. (삽입할때마다 정렬하기때문)

이걸 삽입하는 수만큼 반복하니 시간복잡도는 O(K log K) K: 리스트 수 이다.

Step2)
그리고 PriorityQueue를 poll() 하면서 연결하고, poll()된 노드의 next를 PriorityQueue에 넣는 걸 반복한다.
시간복잡도는 O(N log k) N: 전체 노드 수, K: 링크드 리스트 수 이다.

그럼 총 시간 복잡도는 
O(K log K) + O(N log K) = O(N log K) 가 된다.

 

Step1, 2의 과정을 그냥 단순히, PriorityQueue를 사용하지않고,
배열(Array)에 넣고 sort 한 후, 연결시키는 방법으로 해도되지만,
이는 시간복잡도가 O(N log N)N: 전체 노드 수 가 되어서 PriorityQueue를 사용하는방식이 더 낫다.

 

/**
 * 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) {
        PriorityQueue<ListNode> res = new PriorityQueue<>((a,b) -> Integer.compare(a.val, b.val));

        // PriorityQueue에 각 링크드리스트의 헤드노드 넣기
        for(ListNode node: lists){
            if(node != null){
                res.add(node);
            }
        }

        ListNode head = new ListNode(0);
        ListNode current = head;

        while(!res.isEmpty()){
            ListNode node = res.poll();
            // current 다음으로 queue 젤 앞 node와 연결
            current.next = node;

            // 다음노드로 포인터 이동
            current = node;

            // 가리키는 다음노드가 있다면, PriorityQueue에 넣음
            if(node.next != null){
                res.add(node.next);
            }
        }

        return head.next;
    }
}