📚 10.合并k个有序链表

💻 代码实现

/**
 * @url https://leetcode.cn/problems/merge-k-sorted-lists/description/
 */

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  let _vitrual = new ListNode(0); // 虚拟头结点
  let cur1 = list1,
    cur2 = list2,
    _head = _vitrual;

  while (cur1 && cur2) {
    if (cur1.val < cur2.val) {
      _head.next = cur1;
      cur1 = cur1.next;
      _head = _head.next;
    } else {
      _head.next = cur2;
      cur2 = cur2.next;
      _head = _head.next;
    }
  }
  if (cur1) {
    _head.next = cur1;
    cur1 = cur1.next;
  }
  if (cur2) {
    _head.next = cur2;
    cur2 = cur2.next;
  }
  return _vitrual.next;
}

// function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
//     if (lists.length === 0) return null
//     if (lists.length === 1) return lists[0]
//     let res: ListNode | null = null
//     for (let i = 0; i < lists.length; i++) {
//         res = mergeTwoLists(res, lists[i])
//     }
//     return res
// }

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;
  if (lists.length === 1) {
    return lists[0]; // ps：返回头结点
  }
  const midIndex = Math.floor(lists.length / 2);
  const left = lists.slice(0, midIndex + 1);
  const right = lists.slice(midIndex);
  return mergeTwoLists(mergeKLists(left), mergeKLists(right));
}