I am trying to solve the merge k sorted lists question on leetcode using the non-recursive solution. When I run the code it gives the error as mentioned below. Can you help me to solve the problem? Error is at lists[min_idx] = lists[min_idx]->next;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    
    struct ListNode *result;
    result = (struct ListNode *)malloc(sizeof(struct ListNode));
    result = NULL;
    struct ListNode *p;
    if (!listsSize){
        return result;
    }
    
    int min = INT_MAX;
    int min_idx = 0;
    int cnt=0;
    while (lists){
        for ( int i = 0 ; i<listsSize ; i  ){
            if (lists[i]){
                cnt=0;
                if (lists[i]->val < min){
                    min = lists[i]->val;
                    min_idx = i;
                }
            }
            else {
                cnt  ;
            }
        }
        if (cnt==listsSize){
            break;
        }
        
        struct ListNode *temp;
        temp = (struct ListNode *)malloc(sizeof(struct ListNode));
        temp->val = min;
        temp->next = NULL;
        if (result == NULL){
            result = temp;
            p = temp;
        }
        else {
            p->next = temp;
            p = p->next;
        }
        lists[min_idx] = lists[min_idx]->next;
    }
    return result;
}

ERROR:

Line 52: Char 40: runtime error: member access within null pointer of type 'struct ListNode' [solution.c]. 

CodePudding user response：

For starters even the first two lines produce a memory leak

result = (struct ListNode *)malloc(sizeof(struct ListNode));
result = NULL;

This while loop

while (lists){

can be an infinite loop because by the convention this pointer can not be equal to NULL because it is a pointer to the first element of an array. It can be equal to NULL if the user specially will pass a null pointer to the function that contradicts the function requirement.

This code snippet

    for ( int i = 0 ; i<listsSize ; i  ){
        if (lists[i]){
            cnt=0;
            if (lists[i]->val < min){
                min = lists[i]->val;
                min_idx = i;
            }
        }
        else {
            cnt  ;
        }
    }
    if (cnt==listsSize){
        break;
    }

is unclear and in essence does not make a sense.

The straightforward approach can look for example the following way

struct ListNode * mergeKLists( struct ListNode **lists, size_t listsSize )
{
    struct ListNode *head = NULL;
    struct ListNode **current = &head;

    int empty = 1;

    do
    {
        size_t i = 0;

        while ( i < listsSize && lists[i] == NULL ) i  ;

        empty = i == listsSize;

        if ( !empty )
        {
            size_t min = i;
            
            while (   i != listsSize )
            {
                if ( lists[i] != NULL && lists[i]->val < lists[min]->val )
                {
                    min = i;
                }
            }

            *current = lists[min];
            lists[min] = lists[min]->next;
            ( *current )->next = NULL;
            current = &( *current )->next;              
        }
    } while ( !empty );

    return head;
}

CodePudding user response：

• combine pairwise
• divide & conquer
• (the original array will be overwritten; the result will be in lists[0] )

#include <stddef.h>

struct ListNode {
        struct ListNode *next;
        int val;
        };


struct ListNode *mergeTwolists(struct ListNode *one, struct ListNode *two)
{
struct ListNode *result, **pp;

if (!one) return two;
if (!two) return one;

result = NULL;
for (pp = &result; one && two; pp = &(*pp)->next) {
        if (one->val <= two->val) { *pp = one; one = one->next; }
        else { *pp = two; two = two->next; }
        }
*pp = (one) ? one : two;
return result;
}

struct ListNode *mergeKLists(struct ListNode **lists, unsigned nlist)
{
unsigned src,dst;

for(    ; nlist > 1;    ) {                     // while there are pairs
        for (src=dst=0; src < nlist ; src =2) { // combine pairwise
                if (src 1 >= nlist) lists[dst  ] = lists[src];
                else lists[dst  ] = mergeTwolists(lists[src], lists[src 1]);
                }
        nlist = dst;    // recurse
        }
return lists[0];
}