c语言合并k个已排序的链表

1.问题描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数满足
链表个数满足
每个链表的长度满足 ，每个节点的值满足
要求：时间复杂度

2.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

typedef struct ListNode ListNode;

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

void ListPush(ListNode **head, int val)
{
    ListNode *pre = NULL;
    ListNode *cur = (*head);

    if(cur == NULL)
    {
        *head = (ListNode *)malloc(sizeof(ListNode));

        (*head)->val = val;
        (*head)->next = NULL;

        return;
    }

    while(cur)
    {
        pre = cur;
        cur = cur->next;
    }

    cur = (ListNode *)malloc(sizeof(ListNode));

    pre->next = cur;
    cur->val = val;
    cur->next = NULL;

    return;
}

void ListFree(ListNode **head)
{
    ListNode *next = NULL;
    ListNode *cur = (*head);

    while(cur)
    {
        next = cur->next;

        free(cur);

        cur = next;
    }

    *head = NULL;
}

void ListPrint(ListNode *head)
{
    ListNode *cur = head;

    while(cur)
    {
        printf("%d ", cur->val);

        cur = cur->next;
    }

    printf("\n");
}

struct ListNode *Merge(struct ListNode *pHead1, struct ListNode *pHead2)
{
    struct ListNode *pHead3 = NULL;
    struct ListNode *pPre1 = NULL;
    struct ListNode *pPre2 = NULL;
    struct ListNode *pPre3 = NULL;
    struct ListNode *pCur1 = pHead1;
    struct ListNode *pCur2 = pHead2;
    struct ListNode *pCur3 = NULL;
    struct ListNode *pNext1 = NULL;
    struct ListNode *pNext2 = NULL;

    if(pHead1 == NULL || pHead2 == NULL)
    {
        if(pHead1 == NULL)
        {
            return pHead2;
        }
        else
        {
            return pHead1;
        }
    }

    if(pHead1->val <= pHead2->val)
    {
        pHead3 = pHead1;
        pPre1 = pCur1;
        pCur1 = pCur1->next;
    }
    else
    {
        pHead3 = pHead2;
        pPre2 = pCur2;
        pCur2 = pCur2->next;
    }

    pPre3 = pHead3;
    pPre3->next = NULL;

    while(pCur1 != NULL || pCur2 != NULL)
    {
        if(pCur1 != NULL && pCur2 != NULL)
        {
            if(pCur1->val <= pCur2->val)
            {
                pPre3->next = pCur1;
                pNext1 = pCur1->next;
                pPre3 = pCur1;
                pPre3->next = NULL;
                pPre1 = pCur1;
                pCur1 = pNext1;
            }
            else
            {
                pPre3->next = pCur2;
                pNext2 = pCur2->next;
                pPre3 = pCur2;
                pPre3->next = NULL;
                pPre2 = pCur2;
                pCur2 = pNext2;
            }
        }
        else if(pCur1 != NULL)
        {
            pPre3->next = pCur1;
            pNext1 = pCur1->next;
            pPre3 = pCur1;
            pPre3->next = NULL;
            pPre1 = pCur1;
            pCur1 = pNext1;
        }
        else
        {
            pPre3->next = pCur2;
            pNext2 = pCur2->next;
            pPre3 = pCur2;
            pPre3->next = NULL;
            pPre2 = pCur2;
            pCur2 = pNext2;
        }
    }

    return pHead3;
}

struct ListNode *mergeKLists(struct ListNode **lists, int listsLen)
{
    struct ListNode **c = NULL;
    struct ListNode *d = NULL;
    int a[22] = {0};
    int p;
    int q;
    int w;
    int m;
    int i, j = 1;
    int k;

    if(listsLen > 1000000)
    {
        return NULL;
    }

    if(listsLen == 0)
    {
        return NULL;
    }

    a[0] = 0;

    i = listsLen;

    while(i != 1)
    {
        a[j] = a[j-1] + i;

        j++;

        if(i % 2 == 1)
        {
            i /= 2;
            i++;
        }
        else
        {
            i /= 2;
        }
    }

    a[j] = a[j-1] + 1;
    m = j + 1;

    c = (struct ListNode **)malloc(a[m-1] * sizeof(struct ListNode *));

    for(i=0; i<listsLen; i++)
    {
        c[i] = lists[i];
    }

    for(j=2; j<m; j++)
    {
        p = a[j-2];
        q = a[j-1];
        w = a[j];
        k = 0;

        printf("p = %d, q = %d, w = %d\n", p, q, w);

        if((q - p) % 2 == 0)
        {
            for(i=0; i<w-q; i++)
            {
                c[q+i] = Merge(c[p+k], c[p+k+1]);

                k += 2;
            }
        }
        else
        {
            for(i=0; i<w-q-1; i++)
            {
                c[q+i] = Merge(c[p+k], c[p+k+1]);

                k += 2;
            }

            c[q+i] = c[p+k];

            i++;
        }
    }

    d = c[q];

    free(c);

    return d;
}

int main()
{
    ListNode *head[4] = {NULL};
    ListNode *result = NULL;

    ListPush(&head[0], 1);
    ListPush(&head[0], 2);

    ListPush(&head[1], 1);
    ListPush(&head[1], 4);
    ListPush(&head[1], 5);

    ListPush(&head[2], 6);

    result = mergeKLists(head, 3);

    ListPrint(result);

    ListFree(&result);

    return 0;
}

3.编译源码

$ gcc -o test  test.c -std=c89

4.运行及其结果

$ ./test
p = 0, q = 3, w = 5
p = 3, q = 5, w = 6
1 1 2 4 5 6