PU Merge K Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void insert(struct ListNode **heap, int *top, struct ListNode *node) {
    if (!node) return;
    heap[(*top)++] = node;
    int cur = *top - 1, root = cur / 2;
    while (root && heap[root]->val > heap[cur]->val) {
        struct ListNode *tmp = heap[root];
        heap[root] = heap[cur];
        heap[cur] = tmp;
        cur = root;
        root = cur / 2;
    }
}
struct ListNode *pop(struct ListNode **heap, int *top) {
    struct ListNode *res = heap[1];
    if (res->next) heap[1] = res->next;
    else heap[1] = heap[--*top];
    int cur = 1, left = cur * 2;
    while (left < *top) {
        if (left + 1 < *top && heap[left + 1]->val < heap[left]->val) {
            left = left + 1;
        }
        if (heap[left]->val >= heap[cur]->val) break;
        struct ListNode *tmp = heap[left];
        heap[left] = heap[cur];
        heap[cur] = tmp;
        cur = left;
        left = cur * 2;
    }
    return res;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    struct ListNode **heap = malloc((listsSize + 1) * sizeof(struct ListNode *));
    int top = 1;
    int i;
    for (i = 0; i < listsSize; i++) insert(heap, &top, lists[i]);

    struct ListNode dummy, *p = &dummy;
    while (top > 1) p = p->next = pop(heap, &top);
    p->next = 0;
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void push(struct ListNode **heap, int *top, struct ListNode *node) {
    if (!node) return;
    heap[(*top)++] = node;
    int cur = *top - 1, root = cur / 2;
    while (root && heap[root]->val > heap[cur]->val) {
        struct ListNode *tmp = heap[root];
        heap[root] = heap[cur];
        heap[cur] = tmp;
        cur =  root;
        root = cur / 2;
    }
}
void walkdown(struct ListNode **heap, int *top) {
    int root = 1, target = root * 2;
    while (target < *top) {
        if (target + 1 < *top && heap[target + 1]->val < heap[target]->val) target++;
        if (heap[root]->val <= heap[target]->val) return;
        struct ListNode *tmp = heap[root];
        heap[root] = heap[target];
        heap[target] = tmp;
        root = target;
        target = root * 2;
    }
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize < 1) return 0;
    struct ListNode dummy, *p = &dummy;
    p->next = 0;
    struct ListNode **heap = malloc((listsSize + 1) * sizeof(struct ListNode *));
    int top = 1;
    int i;
    for (i = 0; i < listsSize; i++) push(heap, &top, lists[i]);
    while (top > 1) {
        p->next = heap[1];
        p = p->next;
        if (heap[1]->next) {
            heap[1] = heap[1]->next;
        }
        else {
            heap[1] = heap[--top];
        }
        walkdown(heap, &top);
    }
    free(heap);
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *merge2Lists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode dummy, *p = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        }
        else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return dummy.next;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    struct ListNode dummy, *p = &dummy;
    while (listsSize > 1) {
        int i;
        for (i = 0; i < listsSize / 2; i++) {
            lists[i] = merge2Lists(lists[2 * i], lists[2 * i + 1]);
        }
        if (2 * i + 1 == listsSize) {
            lists[i] = lists[2 * i];
            listsSize = i + 1;
        }
        else listsSize = i;
    }
    return lists[0];
}

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def gen(node):
            while node:
                yield node.val, node
                node = node.next
        head = dummy = ListNode(0)
        for _, node in heapq.merge(*map(gen, lists)):
            head.next = head = node
        return dummy.next

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = [(l.val, l) for l in lists if l]
        heapq.heapify(heap)
        head = dummy = ListNode(0)
        while heap:
            _, node = heapq.heappop(heap)
            if node.next:
                heapq.heappush(heap, (node.next.val, node.next))
            head.next = head = node
        return dummy.next