Merge k sorted Lists – LeetCode #23 (Hard) in C

Home   »   Merge k sorted Lists – LeetCode #23 (Hard) in C

typedef struct {
  int *val; /* this field is malloced and contains the data */
  int size; /* this field contains the number of elements in the val array */
  int maxSize; /* this field contains max number of elements at val */
} data;

void quicksort(int *number,int first,int last);

/* this function makes the adding of data to the structure v, and in the end
it returns 1 if all ok or 0 if there was a problem in the function */
int addElement(data *v, int data);

/******************************************************************************/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
 if (lists == NULL || listsSize == 0) {
    return NULL;
  }
  data v;
  struct ListNode *aux, *answer;
  int i, boolean;
  /* structure initialization */
  v.maxSize = listsSize*20;
  v.size = 0;
  v.val = (int*)calloc(v.maxSize, sizeof (int));
  if (v.val == NULL) {
    return NULL;
  }
  /* structure fulling */
  for (i = 0; i < listsSize; ++i) {
    if (lists[i] != NULL) {
      aux = lists[i];
    } else {
      continue;
    }
    while (aux != NULL) {
      boolean = addElement(&v, aux->val);
      if (boolean == 0) {
        printf("\nThere was an error in the addElements function.");
        return NULL;
      }
      /* advance pointer*/
      aux = aux->next;
    }
  }
  if (v.size == 0) {
    /* free data */
    free(v.val);
    return NULL;
  }
  /* sort data */
  quicksort(v.val,0, v.size-1);
  /* update List */
  for (i = 0; i < v.size; ++i) {
    if (i == 0) {
      /* first node */
      aux = (struct ListNode*)calloc(1, sizeof (struct ListNode));
      if (aux == NULL) {
        printf("\nError in the memory allocation of aux");
        return 0;
      }
      answer = aux;
    } else {
      /* other nodes */
      aux->next = (struct ListNode*)calloc(1, sizeof (struct ListNode));
      if (aux->next == NULL) {
        printf("\nError in the memory allocation of aux2.");
        return 0;
      }
      aux = aux->next;
    }
    aux->val = v.val[i];
  }
  /* free memory */
  free(v.val);
  /* return answer */
  return answer;
}
/******************************************************************************/
void quicksort(int *number,int first,int last){
   int i, j, pivot, temp;
   if(firstnumber[pivot])
            --j;
         if(isize+1 == v->maxSize) {
    /* need more memory */
    v->maxSize*=2;
    v->val = (int*)realloc(v->val, v->maxSize*sizeof(int));
    if (v->val == NULL) {
      return 0;
    }
  }
  /* add data and increment size */
  v->val[v->size] = data;
  v->size+=1;
  /* return without errors */
  return 1;
}
/******************************************************************************/

Leave a Reply

Your email address will not be published. Required fields are marked *