Question

23. Merge k Sorted Lists

中文文档

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

Solutions

Solution 1: Priority Queue (Min Heap)

We can create a min heap $pq$ to maintain the head nodes of all linked lists. Each time, we take out the node with the smallest value from the min heap, add it to the end of the result linked list, and then add the next node of this node to the heap. Repeat the above steps until the heap is empty.

The time complexity is $O(n \times \log k)$, and the space complexity is $O(k)$. Here, $n$ is the total number of all linked list nodes, and $k$ is the number of linked lists given in the problem.

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)
    pq = [head for head in lists if head]
    heapify(pq)
    dummy = cur = ListNode()
    while pq:
      node = heappop(pq)
      if node.next:
        heappush(pq, node.next)
      cur.next = node
      cur = cur.next
    return dummy.next

/**
 * 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<>((a, b) -> a.val - b.val);
    for (ListNode head : lists) {
      if (head != null) {
        pq.offer(head);
      }
    }
    ListNode dummy = new ListNode();
    ListNode cur = dummy;
    while (!pq.isEmpty()) {
      ListNode node = pq.poll();
      if (node.next != null) {
        pq.offer(node.next);
      }
      cur.next = node;
      cur = cur.next;
    }
    return dummy.next;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
    for (auto head : lists) {
      if (head) {
        pq.push(head);
      }
    }
    ListNode* dummy = new ListNode();
    ListNode* cur = dummy;
    while (!pq.empty()) {
      ListNode* node = pq.top();
      pq.pop();
      if (node->next) {
        pq.push(node->next);
      }
      cur->next = node;
      cur = cur->next;
    }
    return dummy->next;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
  pq := hp{}
  for _, head := range lists {
    if head != nil {
      pq = append(pq, head)
    }
  }
  heap.Init(&pq)
  dummy := &ListNode{}
  cur := dummy
  for len(pq) > 0 {
    cur.Next = heap.Pop(&pq).(*ListNode)
    cur = cur.Next
    if cur.Next != nil {
      heap.Push(&pq, cur.Next)
    }
  }
  return dummy.Next
}

type hp []*ListNode

func (h hp) Len() int       { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h hp) Swap(i, j int)    { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)    { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any      { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const pq = new MinPriorityQueue({ priority: (node: ListNode) => node.val });
  for (const head of lists) {
    if (head) {
      pq.enqueue(head);
    }
  }
  const dummy: ListNode = new ListNode();
  let cur: ListNode = dummy;
  while (!pq.isEmpty()) {
    const node = pq.dequeue().element;
    cur.next = node;
    cur = cur.next;
    if (node.next) {
      pq.enqueue(node.next);
    }
  }
  return dummy.next;
}

// 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
//   }
//   }
// }
use std::cmp::Ordering;
use std::collections::BinaryHeap;

impl PartialOrd for ListNode {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}
impl Ord for ListNode {
  fn cmp(&self, other: &Self) -> Ordering {
    self.val.cmp(&other.val).reverse()
  }
}
impl Solution {
  pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
    let mut pq = lists
      .into_iter()
      .filter_map(|head| head)
      .collect::<BinaryHeap<_>>();
    let mut head = None;
    let mut cur = &mut head;
    while let Some(node) = pq.pop() {
      cur = &mut cur.insert(Box::new(ListNode::new(node.val))).next;
      if let Some(next) = node.next {
        pq.push(next);
      }
    }
    head
  }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  const pq = new MinPriorityQueue({ priority: node => node.val });
  for (const head of lists) {
    if (head) {
      pq.enqueue(head);
    }
  }
  const dummy = new ListNode();
  let cur = dummy;
  while (!pq.isEmpty()) {
    const node = pq.dequeue().element;
    cur.next = node;
    cur = cur.next;
    if (node.next) {
      pq.enqueue(node.next);
    }
  }
  return dummy.next;
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   public int val;
 *   public ListNode next;
 *   public ListNode(int val=0, ListNode next=null) {
 *     this.val = val;
 *     this.next = next;
 *   }
 * }
 */
public class Solution {
  public ListNode MergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode, int> pq = new PriorityQueue<ListNode, int>();
    foreach (var head in lists) {
      if (head != null) {
        pq.Enqueue(head, head.val);
      }
    }
    var dummy = new ListNode();
    var cur = dummy;
    while (pq.Count > 0) {
      var node = pq.Dequeue();
      cur.next = node;
      cur = cur.next;
      if (node.next != null) {
        pq.Enqueue(node.next, node.next.val);
      }
    }
    return dummy.next;
  }
}

# Definition for singly-linked list.
class ListNode {
  public $val;
  public $next;
  public function __construct($val = 0, $next = null) {
    $this->val = $val;
    $this->next = $next;
  }
}

class Solution {
  /**
   * @param ListNode[] $lists
   * @return ListNode
   */

  function mergeKLists($lists) {
    $numLists = count($lists);

    if ($numLists === 0) {
      return null;
    }
    while ($numLists > 1) {
      $mid = intval($numLists / 2);
      for ($i = 0; $i < $mid; $i++) {
        $lists[$i] = $this->mergeTwoLists($lists[$i], $lists[$numLists - $i - 1]);
      }
      $numLists = intval(($numLists + 1) / 2);
    }
    return $lists[0];
  }

  function mergeTwoLists($list1, $list2) {
    $dummy = new ListNode(0);
    $current = $dummy;

    while ($list1 != null && $list2 != null) {
      if ($list1->val <= $list2->val) {
        $current->next = $list1;
        $list1 = $list1->next;
      } else {
        $current->next = $list2;
        $list2 = $list2->next;
      }
      $current = $current->next;
    }
    if ($list1 != null) {
      $current->next = $list1;
    } elseif ($list2 != null) {
      $current->next = $list2;
    }
    return $dummy->next;
  }
}