23. Merge k Sorted Lists Hard

1/**
2 * [23] Merge k Sorted Lists
3 *
4 * You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
5 * Merge all the linked-lists into one sorted linked-list and return it.
6 *  
7 * Example 1:
8 * 
9 * Input: lists = [[1,4,5],[1,3,4],[2,6]]
10 * Output: [1,1,2,3,4,4,5,6]
11 * Explanation: The linked-lists are:
12 * [
13 *   1->4->5,
14 *   1->3->4,
15 *   2->6
16 * ]
17 * merging them into one sorted list:
18 * 1->1->2->3->4->4->5->6
19 * 
20 * Example 2:
21 * 
22 * Input: lists = []
23 * Output: []
24 * 
25 * Example 3:
26 * 
27 * Input: lists = [[]]
28 * Output: []
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	k == lists.length
34 * 	0 <= k <= 10^4
35 * 	0 <= lists[i].length <= 500
36 * 	-10^4 <= lists[i][j] <= 10^4
37 * 	lists[i] is sorted in ascending order.
38 * 	The sum of lists[i].length will not exceed 10^4.
39 * 
40 */
41pub struct Solution {}
42use crate::util::linked_list::{ListNode, to_list};
43
44// problem: https://leetcode.com/problems/merge-k-sorted-lists/
45// discuss: https://leetcode.com/problems/merge-k-sorted-lists/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49// Definition for singly-linked list.
50// #[derive(PartialEq, Eq, Clone, Debug)]
51// pub struct ListNode {
52//   pub val: i32,
53//   pub next: Option<Box<ListNode>>
54// }
55// 
56// impl ListNode {
57//   #[inline]
58//   fn new(val: i32) -> Self {
59//     ListNode {
60//       next: None,
61//       val
62//     }
63//   }
64// }
65impl Solution {
66    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
67        Some(Box::new(ListNode::new(0)))
68    }
69}
70
71// submission codes end
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn test_23() {
79    }
80}
81