13ms Pure C solution with min-heap


  • 0
    O

    So few pure C solution for this question
    I think solving questions using pure C is the best way to practice your algorithm because you have no access to
    system libraries

    int HeapAdjust(struct ListNode **heap, int top, int n)
    {
    int j = 2 * top + 1;
    struct ListNode * temp = heap[top];

    while (j < n)
    {
        if (j + 1 < n&&heap[j + 1]->val< heap[j]->val)
            j++;
        if (heap[j]->val >= temp->val)
            break;
        heap[top] = heap[j];
        top = j;
        j = 2 * top + 1;
    }
    heap[top] = temp;
    return 0;
    

    }

    int CreatHeap(struct ListNode **array, int n)
    {
    int i;

    for (i = (n - 2) / 2; i >= 0; i--)
    {
        HeapAdjust(array, i, n);
    }
    return 0;
    

    }

    int HeapDelete(struct ListNode * heap, int n)
    {
    heap[0] = heap[n - 1];
    HeapAdjust(heap, 0, n - 1);
    return 0;
    }
    struct ListNode
    mergeKLists(struct ListNode** lists, int listsSize) {
    struct ListNode* tArr[listsSize];
    int k = 0;
    for (int i=0; i<listsSize; i++) {
    if (lists[i]) {
    tArr[k] = lists[i];
    k++;
    }

    }
    
    listsSize = k;
    
    if (listsSize == 0) {
        return NULL;
    }
    if (listsSize == 1) {
        return tArr[0];
    }
    
    CreatHeap(tArr, listsSize);
    
    struct ListNode* prev = NULL;
    struct ListNode* head = NULL;
    
    while (1) {
        struct ListNode* target = tArr[0];
        tArr[0] =  tArr[0]->next;
        if (!tArr[0]) {
            HeapDelete(tArr, listsSize);
            listsSize --;
        }
        else{
            CreatHeap(tArr, listsSize);
        }
        
        if (head == NULL ) {
            head = prev = target;
        }
        else{
            target->next = NULL;
            if (listsSize == 0) {
                target->next =  NULL;
                prev->next = target;
                break;
            }
            if (listsSize == 1) {
                target->next =  tArr[0];
                prev->next = target;
                break;
            }
            prev->next = target;
            prev = prev->next;
        }
        
    }
    
    return head;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.