description

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

submission

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }

// provide reverse order
impl PartialOrd for ListNode {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        other.val.partial_cmp(&self.val)
    }
}

// provide reverse order
impl Ord for ListNode {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.val.cmp(&self.val)
    }
}

use std::collections::BinaryHeap;

impl Solution {
    // we solve this with priority queue(or BinaryHeap)
    // the intuition is pretty simple, we added every 
    // head node to a heap, we pop a node from the heap
    // at each step, append the node to our result, if
    // the node have following node, add them back to heap
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut head = None;
        let mut tail = &mut head;
        // we want BinaryHeap<T> not BinaryHeap<Option<T>>
        let mut heap = lists.into_iter().filter_map(|list| list).collect::<BinaryHeap<_>>();
        while let Some(node) = heap.pop() {
            // the Option::insert trick to update tail position
            tail = &mut tail.insert(node).next;
            // the Option::take trick to append remaining node 
            if let Some(next) = tail.take() {
                heap.push(next);
            }
        }
        head
    }
}