Merge k Sorted Lists

merge-k-sorted-lists.c

#include <stdio.h>                                                                                                                    
#include <stdlib.h>
#include <limits.h>

#define PARENT(i) (((i+1)>>1)-1)
#define LEFT(i) (((i+1)<<1)-1)
#define RIGHT(i) ((i+1)<<1)

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

void swap(struct ListNode* *a, struct ListNode* *b) {
    struct ListNode* temp = *a;
    *a = *b;
    *b = temp;
}
    
void min_heapify(struct ListNode* *a, int i, int heapsize) {
    int l = LEFT(i);
    int r = RIGHT(i);
    int smallest = i;
    if (l < heapsize && a[l]->val < a[smallest]->val)
        smallest = l;
    if (r < heapsize && a[r]->val < a[smallest]->val)
        smallest = r;
    if (smallest != i) {
        swap(&a[i], &a[smallest]);
    }
}

void build_min_heap(struct ListNode* *a, int length) {
    for (int i = length/2-1; i >= 0; i--) {
        min_heapify(a, i, length);
    }       
}   
    
struct ListNode* process(struct ListNode* *heads, int listsSize) {
    struct ListNode* result = malloc(sizeof(struct ListNode));
    struct ListNode* resultHead = result;
    while (listsSize > 0) {
        build_min_heap(heads, listsSize);
        result->next = heads[0];
        heads[0] = heads[0]->next;
        if (heads[0] == NULL) {
            swap(&heads[0], &heads[listsSize-1]);
            listsSize--;
        }
        result = result->next;
    }
    return resultHead;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize == 0 || lists == NULL) return NULL;
    if (listsSize == 1) return lists[0];
    for (int i = 0; i < listsSize; i++) {
        if (lists[i] == NULL) {    
            struct ListNode* maxNode = malloc(sizeof(struct ListNode));
            maxNode->val = INT_MAX;
            maxNode->next = NULL;
            lists[i] = maxNode;
        }
    }
    struct ListNode* result = process(lists, listsSize);
    return result->next;
}

int main() {
    struct ListNode* n00 = malloc(sizeof(struct ListNode));
    n00->val = 3;
    struct ListNode* n01 = malloc(sizeof(struct ListNode));
    n01->val = 5;
    struct ListNode* n02 = malloc(sizeof(struct ListNode));
    n02->val = 7;
    struct ListNode* n03 = malloc(sizeof(struct ListNode));
    n03->val = 9;
    n00->next = n01;
    n01->next = n02;
    n02->next = n03;
    n03->next = NULL;

    struct ListNode* n10 = malloc(sizeof(struct ListNode));
    n10->val = 2;
    struct ListNode* n11 = malloc(sizeof(struct ListNode));
    n11->val = 4;
    struct ListNode* n12 = malloc(sizeof(struct ListNode));
    n12->val = 6;
    struct ListNode* n13 = malloc(sizeof(struct ListNode));
    n13->val = 8;
    n10->next = n11;
    n11->next = n12;
    n12->next = n13;
    n13->next = NULL;

    struct ListNode* n20 = malloc(sizeof(struct ListNode));
    n20->val = 10;
    n20->next = NULL;

    struct ListNode* n30 = malloc(sizeof(struct ListNode));
    n30->val = 1;
    struct ListNode* n31 = malloc(sizeof(struct ListNode));
    n31->val = 10;
    struct ListNode* n32 = malloc(sizeof(struct ListNode));
    n32->val = 32;
    struct ListNode* n33 = malloc(sizeof(struct ListNode));
    n33->val = 36;
    struct ListNode* n34 = malloc(sizeof(struct ListNode));
    n34->val = 40;
    n30->next = n31;
    n31->next = n32;
    n32->next = n33;
    n33->next = n34;
    n34->next = NULL;

    struct ListNode* n40 = malloc(sizeof(struct ListNode));
    n40->val = 3;
    struct ListNode* n41 = malloc(sizeof(struct ListNode));
    n41->val = 3;
    struct ListNode* n42 = malloc(sizeof(struct ListNode));
    n42->val = 3;
    struct ListNode* n43 = malloc(sizeof(struct ListNode));
    n43->val = 3;
    struct ListNode* n44 = malloc(sizeof(struct ListNode));
    n44->val = 3;
    n40->next = n41;
    n41->next = n42;
    n42->next = n43;
    n43->next = n44;
    n44->next = NULL;

    int n = 5;
    struct ListNode* *lists = malloc(sizeof(struct ListNode*)*n);
    lists[0] = n00;
    lists[1] = n10;
    lists[2] = n20;
    lists[3] = n30;
    lists[4] = n40;

    struct ListNode* result = mergeKLists(lists, n);
    while (result != NULL) {
        printf("%d\t", result->val);
        result = result->next;
    }
    printf("\n");
    return 0;
}