Merge k Sorted Lists

꿀잠마스터 2026. 8. 25. 00:40

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

Merge k Sorted Lists - LeetCode

Can you solve this real interview question? 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: lis

leetcode.com

주어진 ListNode 리스트 배열의 모든 값들을 오름차순으로 변경해야한다.
값을 기준으로 오름차순으로 하면 되기 때문에 PriorityQueue 사용시 쉽게 정렬할 수 있다.
정렬한 이후에는 poll 하며 순서대로 head에 next를 연결하면 된다.

import java.util.*;  
/**
 * 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<>((node1, node2) -> node2.val - node1.val);  
        for(ListNode node: lists){  
            while(node != null){  
                pq.add(node);  
                node = node.next;  
            }  
        }  
  
        ListNode head = null;  
        ListNode next = null;  
        while(!pq.isEmpty()){  
            head = pq.poll();  
            head.next = next;  
            next = head;  
        }  
  
        return head;  
    }  
}