Merge K ascending linked lists

The title

Merge K ascending linked lists

Train of thought

When we think about merging k ordered lists, we can simplify the complexity first, and think about how to merge two ordered lists first. 21. Merge two ordered lists.

Merging two ordered lists is relatively simple, with two caveat:

1. Don’t forget to define a sentinel node to store the merged linked list.
2. Don’t forget to add the two lists that are surplus after the comparison to the end of the result list.

const merge = (list_1, list_2) => {
  const sentinelNode = new ListNode(0);
  let p = sentinelNode;

  while (list_1 && list_2) {
    if (list_1.val < list_2.val) {
      p.next = list_1;
      list_1 = list_1.next;
    } else {
      p.next = list_2;
      list_2 = list_2.next;
    }
    p = p.next;
  }

  p.next = list_1 ? list_1 : list_2;
  return sentinelNode.next;
};
Copy the code

Then you can consider how to divide and conquer, as shown below:

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode[]} lists
 * @return {ListNode}* /
var mergeKLists = function (lists) {
  /* Divide and rule */
  if (lists.length <= 1) return lists[0] | |null;
  const newLists = [];
  for (let i = 0; i < lists.length; i += 2) {
    newLists.push(merge(lists[i], lists[i + 1] | |null));
  }
  return mergeKLists(newLists);
};

const merge = (list_1, list_2) = > {
  const sentinelNode = new ListNode(0);
  let p = sentinelNode;

  while (list_1 && list_2) {
    if (list_1.val < list_2.val) {
      p.next = list_1;
      list_1 = list_1.next;
    } else {
      p.next = list_2;
      list_2 = list_2.next;
    }
    p = p.next;
  }

  p.next = list_1 ? list_1 : list_2;
  return sentinelNode.next;
};
Copy the code

Finally, there are many suggestions 😜, Thanks – (· ω ·) Blue