My 46 lines in c code, use qsort fuction. 388ms


  • 0
    X
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
     
    int comval(const void *p1, const void *p2) {
        int re;
        int a = (*(struct ListNode * const *)p1)->val;
        int b = (*(struct ListNode * const *)p2)->val;
        if (a == b) {
            return 0;
        } else if (a < b) {
            return -1;
        } else {
            return 1;
        }
    }
    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
        if (lists == NULL || listsSize == 0) return NULL;
        if (listsSize == 1) return *lists;
        struct ListNode **root = calloc(listsSize*2, sizeof(struct ListNode *));
        int len = listsSize*2;
        int i;
        int j;
        for(i=0,j=0; i < listsSize; i++) {
            struct ListNode *cur = lists[i];
            while(cur) {
                root[j++] = cur;
                cur = cur->next;
                if (j == len) {
                    root = realloc(root, sizeof(struct ListNode*)*len*2);
                    len *=2;
                }
            }
        }
        if (j == 0) return NULL;
        qsort(root, j, sizeof(struct ListNode*), comval);
        for (i=0; i < j-1; i++) {
            root[i]->next = root[i+1];
        }
        root[j-1]->next = NULL;
        return root[0];
    }

Log in to reply
 

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