23. Merged k sorted lists

23_solution1_sorting.c

#include "list_node.h"
#include <stdlib.h>

static int cmp_int(const void *a, const void *b) {
  int x = *(const int *)a, y = *(const int *)b;
  return (x > y) - (x < y);
}

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
  // 1. collect every value from every list
  int count = 0;
  for (int i = 0; i < listsSize; i++)
    for (struct ListNode *p = lists[i]; p; p = p->next)
      count++;

  if (count == 0)
    return NULL;

  int *vals = malloc(count * sizeof(int));
  int k = 0;
  for (int i = 0; i < listsSize; i++)
    for (struct ListNode *p = lists[i]; p; p = p->next)
      vals[k++] = p->val;

  // 2. sort them
  qsort(vals, count, sizeof(int), cmp_int);

  // 3. rebuild a new list
  struct ListNode dummy;
  struct ListNode *cur = &dummy;
  for (int i = 0; i < count; i++) {
    cur->next = malloc(sizeof(struct ListNode));
    cur = cur->next;
    cur->val = vals[i];
    cur->next = NULL;
  }

  free(vals);
  return dummy.next;
}

23_solution2_minheap.c

#include "list_node.h"
#include <stdlib.h>

// array-backed binary min-heap of node pointers keyed on val
static void sift_up(struct ListNode **h, int i) {
  while (i > 0) {
    int parent = (i - 1) / 2;
    if (h[parent]->val <= h[i]->val)
      break;
    struct ListNode *t = h[parent];
    h[parent] = h[i];
    h[i] = t;
    i = parent;
  }
}

static void sift_down(struct ListNode **h, int size, int i) {
  for (;;) {
    int smallest = i, l = 2 * i + 1, r = l + 1;
    if (l < size && h[l]->val < h[smallest]->val)
      smallest = l;
    if (r < size && h[r]->val < h[smallest]->val)
      smallest = r;
    if (smallest == i)
      return;
    struct ListNode *t = h[smallest];
    h[smallest] = h[i];
    h[i] = t;
    i = smallest;
  }
}

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
  struct ListNode **heap = malloc((listsSize > 0 ? listsSize : 1) * sizeof(*heap));
  int size = 0;

  // seed with the head of each non-empty list
  for (int i = 0; i < listsSize; i++) {
    if (lists[i]) {
      heap[size] = lists[i];
      sift_up(heap, size++);
    }
  }

  struct ListNode dummy;
  struct ListNode *cur = &dummy;

  while (size > 0) {
    struct ListNode *smallest = heap[0];

    cur->next = smallest;
    cur = cur->next;

    // replace the root with its successor (or the last node) and restore order
    heap[0] = smallest->next ? smallest->next : heap[--size];
    sift_down(heap, size, 0);
  }

  free(heap);
  cur->next = NULL;
  return dummy.next;
}

23_solution3_divide_and_conquer.c

#include "list_node.h"

static struct ListNode *mergeTwo(struct ListNode *a, struct ListNode *b) {
  struct ListNode dummy;
  struct ListNode *cur = &dummy;
  while (a && b) {
    if (a->val <= b->val) {
      cur->next = a;
      a = a->next;
    } else {
      cur->next = b;
      b = b->next;
    }
    cur = cur->next;
  }
  cur->next = a ? a : b;
  return dummy.next;
}

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
  if (listsSize == 0)
    return NULL;

  for (int step = 1; step < listsSize; step *= 2)
    for (int i = 0; i + step < listsSize; i += 2 * step)
      lists[i] = mergeTwo(lists[i], lists[i + step]);

  return lists[0];
}

list_node.h

#pragma once

#include <stddef.h>

// Definition for singly-linked list.
struct ListNode {
  int val;
  struct ListNode *next;
};

23_solution1_sorting.cpp

#include "list_node.h"
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  ListNode *mergeKLists(vector<ListNode *> &lists) {
    // 1. collect every value from every list
    vector<int> vals;
    for (ListNode *head : lists)
      for (ListNode *p = head; p; p = p->next)
        vals.push_back(p->val);

    // 2. sort them
    sort(vals.begin(), vals.end());

    // 3. rebuild a new list
    ListNode dummy;
    ListNode *cur = &dummy;
    for (int v : vals) {
      cur->next = new ListNode(v);
      cur = cur->next;
    }

    return dummy.next;
  }
};

23_solution2_minheap.cpp

#include "list_node.h"
#include <queue>
#include <vector>

using namespace std;

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)> minHeap(cmp);

    // seed with the head of each non-empty list
    for (ListNode *head : lists)
      if (head)
        minHeap.push(head);

    ListNode dummy;
    ListNode *cur = &dummy;

    while (!minHeap.empty()) {
      ListNode *smallest = minHeap.top();
      minHeap.pop();

      cur->next = smallest;
      cur = cur->next;

      // the only new candidate is the successor of the node we just took
      if (smallest->next)
        minHeap.push(smallest->next);
    }

    return dummy.next;
  }
};

23_solution3_divide_and_conquer.cpp

#include "list_node.h"
#include <vector>

using namespace std;

class Solution {
  ListNode *mergeTwo(ListNode *a, ListNode *b) {
    ListNode dummy;
    ListNode *cur = &dummy;
    while (a && b) {
      if (a->val <= b->val) {
        cur->next = a;
        a = a->next;
      } else {
        cur->next = b;
        b = b->next;
      }
      cur = cur->next;
    }
    cur->next = a ? a : b;
    return dummy.next;
  }

public:
  ListNode *mergeKLists(vector<ListNode *> &lists) {
    int n = lists.size();
    if (n == 0)
      return nullptr;

    for (int step = 1; step < n; step *= 2)
      for (int i = 0; i + step < n; i += 2 * step)
        lists[i] = mergeTwo(lists[i], lists[i + step]);

    return lists[0];
  }
};

list_node.h

#pragma once

// 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) {}
};

23_solution1_sorting.go

package linkedlists

import "sort"

func mergeKLists(lists []*ListNode) *ListNode {
    // 1. collect every value from every list
    vals := []int{}
    for _, head := range lists {
        for p := head; p != nil; p = p.Next {
            vals = append(vals, p.Val)
        }
    }

    // 2. sort them
    sort.Ints(vals)

    // 3. rebuild a new list
    dummy := &ListNode{}
    cur := dummy
    for _, v := range vals {
        cur.Next = &ListNode{Val: v}
        cur = cur.Next
    }

    return dummy.Next
}

23_solution2_minheap.go

package linkedlists

import "container/heap"

type nodeHeap []*ListNode

func (h nodeHeap) Len() int           { return len(h) }
func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h nodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x any)        { *h = append(*h, x.(*ListNode)) }
func (h *nodeHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    minHeap := &nodeHeap{}

    // seed with the head of each non-empty list
    for _, head := range lists {
        if head != nil {
            *minHeap = append(*minHeap, head)
        }
    }
    heap.Init(minHeap)

    dummy := &ListNode{}
    cur := dummy

    for minHeap.Len() > 0 {
        smallest := heap.Pop(minHeap).(*ListNode)

        cur.Next = smallest
        cur = cur.Next

        // the only new candidate is the successor of the node we just took
        if smallest.Next != nil {
            heap.Push(minHeap, smallest.Next)
        }
    }

    return dummy.Next
}

23_solution3_divide_and_conquer.go

package linkedlists

func mergeTwo(a, b *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for a != nil && b != nil {
        if a.Val <= b.Val {
            cur.Next = a
            a = a.Next
        } else {
            cur.Next = b
            b = b.Next
        }
        cur = cur.Next
    }
    if a != nil {
        cur.Next = a
    } else {
        cur.Next = b
    }
    return dummy.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if n == 0 {
        return nil
    }

    for step := 1; step < n; step *= 2 {
        for i := 0; i+step < n; i += 2 * step {
            lists[i] = mergeTwo(lists[i], lists[i+step])
        }
    }

    return lists[0]
}

list_node.go

package linkedlists

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

23_solution1_sorting.java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 1. collect every value from every list
        List<Integer> vals = new ArrayList<>();
        for (ListNode head : lists)
            for (ListNode p = head; p != null; p = p.next)
                vals.add(p.val);

        // 2. sort them
        int[] sorted = vals.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(sorted);

        // 3. rebuild a new list
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        for (int v : sorted) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }

        return dummy.next;
    }
}

23_solution2_minheap.java

import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        // seed with the head of each non-empty list
        for (ListNode head : lists)
            if (head != null)
                minHeap.add(head);

        ListNode dummy = new ListNode();
        ListNode cur = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();

            cur.next = smallest;
            cur = cur.next;

            // the only new candidate is the successor of the node we just took
            if (smallest.next != null)
                minHeap.add(smallest.next);
        }

        return dummy.next;
    }
}

23_solution3_divide_and_conquer.java

class Solution {
    private ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) {
                cur.next = a;
                a = a.next;
            } else {
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }
        cur.next = (a != null) ? a : b;
        return dummy.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0)
            return null;

        for (int step = 1; step < n; step *= 2)
            for (int i = 0; i + step < n; i += 2 * step)
                lists[i] = mergeTwo(lists[i], lists[i + step]);

        return lists[0];
    }
}

ListNode.java

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

23_solution1_sorting.js

const ListNode = require("./list_node");

var mergeKLists = function (lists) {
  // 1. collect every value from every list
  const vals = [];
  for (let head of lists)
    for (let p = head; p !== null; p = p.next) vals.push(p.val);

  // 2. sort them
  vals.sort((a, b) => a - b);

  // 3. rebuild a new list
  const dummy = new ListNode();
  let cur = dummy;
  for (const v of vals) {
    cur.next = new ListNode(v);
    cur = cur.next;
  }

  return dummy.next;
};

23_solution2_minheap.js

const ListNode = require("./list_node");

// minimal binary min-heap of ListNodes keyed on val
class MinHeap {
  constructor() {
    this.data = [];
  }

  get size() {
    return this.data.length;
  }

  push(node) {
    const d = this.data;
    d.push(node);
    let i = d.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (d[parent].val <= d[i].val) break;
      [d[parent], d[i]] = [d[i], d[parent]];
      i = parent;
    }
  }

  pop() {
    const d = this.data;
    const top = d[0];
    const last = d.pop();
    if (d.length > 0) {
      d[0] = last;
      let i = 0;
      for (;;) {
        let smallest = i;
        const l = 2 * i + 1;
        const r = l + 1;
        if (l < d.length && d[l].val < d[smallest].val) smallest = l;
        if (r < d.length && d[r].val < d[smallest].val) smallest = r;
        if (smallest === i) break;
        [d[smallest], d[i]] = [d[i], d[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

var mergeKLists = function (lists) {
  const minHeap = new MinHeap();

  // seed with the head of each non-empty list
  for (const head of lists) if (head !== null) minHeap.push(head);

  const dummy = new ListNode();
  let cur = dummy;

  while (minHeap.size > 0) {
    const smallest = minHeap.pop();

    cur.next = smallest;
    cur = cur.next;

    // the only new candidate is the successor of the node we just took
    if (smallest.next !== null) minHeap.push(smallest.next);
  }

  return dummy.next;
};

23_solution3_divide_and_conquer.js

const ListNode = require("./list_node");

function mergeTwo(a, b) {
  const dummy = new ListNode();
  let cur = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) {
      cur.next = a;
      a = a.next;
    } else {
      cur.next = b;
      b = b.next;
    }
    cur = cur.next;
  }
  cur.next = a !== null ? a : b;
  return dummy.next;
}

var mergeKLists = function (lists) {
  const n = lists.length;
  if (n === 0) return null;

  for (let step = 1; step < n; step *= 2)
    for (let i = 0; i + step < n; i += 2 * step)
      lists[i] = mergeTwo(lists[i], lists[i + step]);

  return lists[0];
};

list_node.js

// Definition for singly-linked list.
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

module.exports = ListNode;

23_solution1_sorting.py

from typing import List, Optional

from list_node import ListNode


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 1. collect every value from every list
        vals = []
        for head in lists:
            while head:
                vals.append(head.val)
                head = head.next

        # 2. sort them
        vals.sort()

        # 3. rebuild a new list
        dummy = ListNode()
        cur = dummy
        for v in vals:
            cur.next = ListNode(v)
            cur = cur.next

        return dummy.next

23_solution2_minheap.py

import heapq
from typing import List, Optional

from list_node import ListNode


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # (val, index, node): the index breaks ties so nodes are never compared
        min_heap = [(head.val, i, head) for i, head in enumerate(lists) if head]
        heapq.heapify(min_heap)

        dummy = ListNode()
        cur = dummy

        while min_heap:
            _, i, smallest = heapq.heappop(min_heap)

            cur.next = smallest
            cur = cur.next

            # the only new candidate is the successor of the node we just took
            if smallest.next:
                heapq.heappush(min_heap, (smallest.next.val, i, smallest.next))

        return dummy.next

23_solution3_divide_and_conquer.py

from typing import List, Optional

from list_node import ListNode


class Solution:
    def _merge_two(self, a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        while a and b:
            if a.val <= b.val:
                cur.next = a
                a = a.next
            else:
                cur.next = b
                b = b.next
            cur = cur.next
        cur.next = a if a else b
        return dummy.next

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        n = len(lists)
        if n == 0:
            return None

        step = 1
        while step < n:
            for i in range(0, n - step, 2 * step):
                lists[i] = self._merge_two(lists[i], lists[i + step])
            step *= 2

        return lists[0]

list_node.py

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

23_solution1_sorting.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        // 1. collect every value from every list
        let mut vals = Vec::new();
        for head in &lists {
            let mut p = head;
            while let Some(node) = p {
                vals.push(node.val);
                p = &node.next;
            }
        }

        // 2. sort them
        vals.sort_unstable();

        // 3. rebuild a new list (back to front, so no tail pointer is needed)
        let mut head = None;
        for v in vals.into_iter().rev() {
            let mut node = Box::new(ListNode::new(v));
            node.next = head;
            head = Some(node);
        }

        head
    }
}

23_solution2_minheap.rs

use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;

use crate::list_node::ListNode;

// orders nodes by val only, so ListNode itself needs no Ord
struct HeapNode(Box<ListNode>);

impl PartialEq for HeapNode {
    fn eq(&self, other: &Self) -> bool {
        self.0.val == other.0.val
    }
}
impl Eq for HeapNode {}
impl PartialOrd for HeapNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Ord for HeapNode {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.val.cmp(&other.0.val)
    }
}

impl Solution {
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        // seed with the head of each non-empty list
        let mut min_heap: BinaryHeap<Reverse<HeapNode>> = lists
            .into_iter()
            .flatten()
            .map(|head| Reverse(HeapNode(head)))
            .collect();

        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        while let Some(Reverse(HeapNode(mut smallest))) = min_heap.pop() {
            // the only new candidate is the successor of the node we just took
            if let Some(next) = smallest.next.take() {
                min_heap.push(Reverse(HeapNode(next)));
            }

            tail.next = Some(smallest);
            tail = tail.next.as_mut().unwrap();
        }

        dummy.next
    }
}

23_solution3_divide_and_conquer.rs

use crate::list_node::ListNode;

impl Solution {
    fn merge_two(
        a: Option<Box<ListNode>>,
        b: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match (a, b) {
            (None, b) => b,
            (a, None) => a,
            (Some(mut a), Some(b)) if a.val <= b.val => {
                a.next = Self::merge_two(a.next.take(), Some(b));
                Some(a)
            }
            (Some(a), Some(mut b)) => {
                b.next = Self::merge_two(Some(a), b.next.take());
                Some(b)
            }
        }
    }

    pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let n = lists.len();
        if n == 0 {
            return None;
        }

        let mut step = 1;
        while step < n {
            let mut i = 0;
            while i + step < n {
                let a = lists[i].take();
                let b = lists[i + step].take();
                lists[i] = Self::merge_two(a, b);
                i += 2 * step;
            }
            step *= 2;
        }

        lists[0].take()
    }
}

list_node.rs

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

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}