Description (leetcode)

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 <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 10^4.

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;

// 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
impl Solution {
    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().flatten().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
    }
}