c语言合并两个排序的链表

1.问题描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： ，
要求：空间复杂度 ，时间复杂度

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;
}

int main()
{
    ListNode *head1 = NULL;
    ListNode *head2 = NULL;
    ListNode *head3 = NULL;

    ListPush(&head1, -1);
    ListPush(&head1, 2);
    ListPush(&head1, 4);
    ListPush(&head1, 4);
    ListPush(&head1, 4);

    ListPush(&head2, 1);
    ListPush(&head2, 3);
    ListPush(&head2, 4);
    ListPush(&head2, 5);

    head3 = Merge(head1, head2);

    ListPrint(head3);

    ListFree(&head3);

    return 0;
}

3.编译源码

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

4.运行及其结果

$ ./test
-1 1 2 3 4 4 4 4 5