讨论/《腾讯》 - 合并K个排序链表/
《腾讯》 - 合并K个排序链表
共 2 个回复
var mergeTwoList = function (l1, l2) {
    if (!l1) {
        return l2
    }
    if (!l2) {
        return l1
    }
    let dummyHead = new ListNode(-1, null)
    const orig = dummyHead
    while (l1 != null && l2 != null) {
        const v1 = l1.val
        const v2 = l2.val
        if (v1 < v2) {
            dummyHead.next = new ListNode(v1)
            dummyHead = dummyHead.next
            l1 = l1.next
            continue
        }
        dummyHead.next = new ListNode(v2)
        dummyHead = dummyHead.next
        l2 = l2.next
    }

    dummyHead.next = l1 == null ? l2 : l1

    return orig.next
}

function merge(lists, l, r) {
    if (l == r) return lists[l];
    if (l > r) return null;
    let mid = (l + r) >> 1;
    return mergeTwoList(merge(lists, l, mid), merge(lists, mid + 1, r));
}

function mergeKLists(lists) {
    return merge(lists, 0, lists.length - 1);
}

/**

  • 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) {}
    
  • };
    /
    class Solution {
    public:
    ListNode
    mergeKLists(vector<ListNode*>& lists) {

     if(lists.size()==0) return nullptr;
    
     ListNode* head = new ListNode();
     ListNode* ptr = head;
    
     while(true){
    
         int list_min = INT_MAX;
         int cur_list = 0;
         for(int i=0; i<lists.size(); ++i){
             if(lists[i]==nullptr){
                 continue;
             }
    
             if(lists[i]->val < list_min){
                 list_min = lists[i]->val;
                 cur_list = i;
             }
         }
         if(list_min == INT_MAX){
             break;
         }
    
         lists[cur_list] = lists[cur_list]->next;
         ptr->next = new ListNode(list_min);
         ptr = ptr->next;
    
         bool allnull = true;
         for(int i=0; i<lists.size();++i){
             if(lists[i]!=nullptr){
                 allnull = false;
                 break;
             }
         }
    
         if(allnull) break;
     }
    
     ptr = head->next;
     delete head;
     return ptr;
    

    }
    };