23. Merge k Sorted Lists

Problem From.

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

오늘 문제는 linked list 를 원소로 가지는 list 가 주어졌을때, 그 안의 원소를 오름차순으로 나열하여 반환하는 문제였다.

이 문제는 priority queue 를 쓰면 쉽게 풀 수 있는데, priority queue 는 queue 안에 원소를 넣으면 오름차순 또는 내림차순으로 자동으로 정렬되게 할 수 있는 자료구조이다.

list 안에 주어진 linked list 를 priority queue 안에 넣은뒤 다시 빼내는 방식으로 문제를 풀었다.

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        val pq = PriorityQueue<ListNode>{ a,b -> Integer.compare(a.`val`, b.`val`) }
        for (n in lists) {
            n?.let { pq.offer(it) }
        }
        val head = ListNode()
        var curr = head
        while (!pq.isEmpty()) {
            val min = pq.poll()
            curr.next = min
            min?.next?.let {
                pq.offer(it)
            }
            curr = curr.next
        }
        return head.next
    }
}