链表合并

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

//定义链表结点
typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;

void ListAdd(ListNode** tail, ListNode* node)
{
    (*tail)->next = node;
    *tail = node;
}

//合并2个有序链表
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
    //判断是需要进行排序
    if (!list1)
    {
        return list2;
    }
    if (!list2)
    {
        return list1;
    }

    //创建一个新链表，并初始化head、tail为NULL
    ListNode* head = NULL;
    ListNode* tail = NULL;

    //遍历2个链表，同时进行比较，将val较小的结点连接至新链表中
    while (list1 && list2)
    {
        if (list1->val > list2->val)
        {
            //将list2链接至新链表
            if (head == NULL)
            {
                head = tail = list2;
            }
            else
            {
                ListAdd(&tail, list2);
            }
            list2 = list2->next;
        }
        else
        {
            //将list1链接至新链表
            if (head == NULL)
            {
                head = tail = list1;
            }
            else
            {
                ListAdd(&tail, list1);
            }
            list1 = list1->next;
        }
    }
    //链接剩余结点
    if (!list1)
    {
        //链接list2
        ListAdd(&tail, list2);
    }
    else
    {
        //链接list1
        ListAdd(&tail, list1);
    }

    return head;
}

//创建新结点,返回新结点地址
ListNode* ListBuyNode(int x)
{
    //创建新结点
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode)
    {
        perror("malloc fail!");
        exit(1);
    }
    newNode->val = x;
    newNode->next = NULL;

    return newNode;
}

//打印链表
void ListPrint(ListNode* phead)
{
    //判断是否需要打印，以免后续解引用时造成越界访问
    if (phead == NULL)
    {
        return;
    }

    ListNode* pcur = phead;
    while (pcur != NULL)
    {
        printf("%d ", pcur->val);
        pcur = pcur->next;
    }
}

//释放链表
void ListFree(ListNode* phead)
{
    //判断是否有结点以供释放
    if (phead)
    {
        return;
    }

    ListNode* pcur = phead;
    ListNode* prev = NULL;

    while (pcur != NULL)
    {
        prev = pcur;
        pcur = pcur->next;
        free(prev);
    }
}

int main()
{
    ListNode* head1 = NULL;
    ListNode* head2 = NULL;
    ListNode* tail1 = NULL;
    ListNode* tail2 = NULL;
    ListNode* mergeHead = NULL;
    int input = 0;
    char judge = 0;

    //录入链表1
    judge = 1;
    while (judge != '\n')
    {
        scanf("%d", &input);
        judge = getchar();

        if (head1 == NULL)
        {
            //链表为空时，同时更新头结点指针
            head1 = tail1 = ListBuyNode(input);
        }
        else
        {
            //链表不为空，只更新尾结点指针即可
            tail1->next = ListBuyNode(input);
            tail1 = tail1->next;
        }
    }

    //录入链表2
    judge = 1;
    while (judge != '\n')
    {
        scanf("%d", &input);
        judge = getchar();

        if (head2 == NULL)
        {
            //链表为空时，同时更新头结点指针
            head2 = tail2 = ListBuyNode(input);
        }
        else
        {
            //链表不为空，只更新尾结点指针即可
            tail2->next = ListBuyNode(input);
            tail2 = tail2->next;
        }
    }

    //合并链表
    mergeHead = mergeTwoLists(head1, head2);

    //打印链表
    ListPrint(mergeHead);

    //释放链表
    ListFree(mergeHead);

    return 0;
}