Merge k Sorted Lists - 《LeetCode》

Problem
- Example
- Constraints
Solution

Problem

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

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

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

Constraints

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won’t exceed 10^4.

Solution

一个一个比较

/**
* 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 mergeTwoLists = (list1, list2) => {
     if (!list1) {
         return list2;
     }
     if (!list2) {
         return list1;
     }

     let cur, res;

     let n1 = list1, n2 = list2;

     while (n1 || n2) {
         let n;
         if (n1 && n2) {
             if (n1.val < n2.val) {
                 n = n1;
                 n1 = n1.next;
             } else {
                 n = n2;
                 n2 = n2.next;
             }
         } else {
             if (n1) {
                 n = n1;
                 n1 = n1.next;
             } else {
                 n = n2;
                 n2 = n2.next;
             }
         }

         if (!res) {
             res = {
                 val: n.val,
                 next: null
             }
             cur = res;
         } else {
             cur.next = {
                 val: n.val,
                 next: null
             }
             cur = cur.next;
         }
     }

     return res;
 }

 if (lists.length > 0) {
     let res = lists[0];
     for (let i = 1; i < lists.length; i++) {
         res = mergeTwoLists(res, lists[i]);
     }
     return res;
 } else {
     return null;
 }
};

遍历所有链表，将值存储在数组中，然后排序数组中的数字，重新构建新的链表。