23. Merge k Sorted Lists

문제

 

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: []

 

Constraints:

• 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.

 

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

 

 

풀이

이전에 풀었던 Merge Two Sorted Lists 문제와 유사하다보니, 동일하게 풀어보려고 했으나 3개는 크기 비교 위치 잡기가 애매해서 한참 고민했다.

단순히 while문 안에 for문으로 lists의 개수만큼 돌면서 확인하자니 먼저 null까지 확인한 list 때문에 확인이 어려웠었다.

한참 고민하다가 그냥 계속 적은걸 넣어놓을 수 있을까? 하는 생각에 우선순위 큐가 생각났고, 이를 이용하여 lists의 값들을 모두 우선순위 큐에 집어넣어서 알아서 정렬되게끔 했다.

 

더미 노드를 하나 만들고, lists 내에 0번 index부터 쭉 집어넣고 큐에서 하나식 빼서 연결하도록 하였다.

시간복잡도도 우선순위 큐 사용하면 큐에 넣을 때 log(k)에 배열 개수  k를 합친 klog(k) 이고, 큐에서 하나씩 빼서 넣는 k을 합하면 2*klog(k)로 나쁘지 않지 않을까 생각한다.

 

코드

/**
 * 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> pq = new PriorityQueue<>(new Comparator<ListNode>() {
        	@Override
			public int compare(ListNode o1, ListNode o2) {
				return o1.val - o2.val;
			}
        });
        
        for(int i = 0; i< lists.length ; i++) {
        	if(lists[i] != null) {        		
        		pq.add(lists[i]);
        	}
        }
        
        ListNode dummy = new ListNode();
        ListNode idx = dummy;
        
        while(!pq.isEmpty()) {
        	ListNode node = pq.poll();
        	
        	if(node.next != null)
        		pq.add(node.next);
        	
        	idx.next = node;
        	idx = idx.next;
        }
        
        return dummy.next;
    }
}

 

 

결과

Runtime : 4 ms

Memory Usage : 44.35 MB