Merge K Sorted Linked Lists

[jsartisan]

Info

difficulty: hard
title: Merge K Sorted Linked Lists
type: question
template: typescript
tags: javascript, blind75, linked-list, heap, divide-and-conquer

Question

You are given an array containing k sorted linked lists, where each list maintains ascending order.

Create and return a new sorted linked list that combines all nodes from the input lists while maintaining the sorted order.

Constraints:

• 0 ≤ k (number of lists) ≤ 1000
• 0 ≤ length of each list ≤ 100
• -1000 ≤ value in each node ≤ 1000

Examples:

// Example 1:
const lists1 = [
  createList([1, 2, 4]),
  createList([1, 3, 5]),
  createList([3, 6])
];
console.log(mergeKLists(lists1));
// Output: [1, 1, 2, 3, 3, 4, 5, 6]

// Example 2:
const lists2: ListNode[] = [];
console.log(mergeKLists(lists2));
// Output: null

// Example 3:
const lists3 = [createList([])];
console.log(mergeKLists(lists3));
// Output: null

Template

index.ts

export 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;
  }
}

export function mergeKLists(lists: Array<ListNode | null>): ListNode | null {

}

index.test.ts

import { ListNode, mergeKLists } from './index';

describe('mergeKLists', () => {
  // Helper function to create linked list from array
  function createList(arr: number[]): ListNode | null {
    if (!arr.length) return null;
    const head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
      current.next = new ListNode(arr[i]);
      current = current.next;
    }
    return head;
  }

  // Helper function to convert linked list to array
  function listToArray(head: ListNode | null): number[] {
    const result = [];
    let current = head;
    while (current) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }

  test('Example 1: Multiple non-empty lists', () => {
    const lists = [
      createList([1, 2, 4]),
      createList([1, 3, 5]),
      createList([3, 6])
    ];
    expect(listToArray(mergeKLists(lists))).toEqual([1, 1, 2, 3, 3, 4, 5, 6]);
  });

  test('Example 2: Empty array of lists', () => {
    expect(mergeKLists([])).toBeNull();
  });

  test('Example 3: Array with empty list', () => {
    expect(mergeKLists([null])).toBeNull();
  });

  test('Single list', () => {
    const lists = [createList([1, 2, 3])];
    expect(listToArray(mergeKLists(lists))).toEqual([1, 2, 3]);
  });

  test('Lists with different lengths', () => {
    const lists = [
      createList([1]),
      createList([1, 2, 3]),
      createList([2])
    ];
    expect(listToArray(mergeKLists(lists))).toEqual([1, 1, 2, 2, 3]);
  });

  test('Lists with negative numbers', () => {
    const lists = [
      createList([-2, 1, 4]),
      createList([-1, 3, 4]),
      createList([2])
    ];
    expect(listToArray(mergeKLists(lists))).toEqual([-2, -1, 1, 2, 3, 4, 4]);
  });
});

[github-actions[bot]]

234 - Pull Request updated.