两个有序单链表的合并（数据结构）

将两个非递减有序单链表合并成一个非递减有序单链表；
输入样例：
5
1 3 5 7 9
6
2 3 4 6 8 10
输出样例：
1 2 3 3 4 5 6 7 8 9 10

补全如下代码

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node* next;
};
struct Node* createNode(int data)//初始化链表
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL)
    {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void insertNode(struct Node* head, int data)//将数据加入成为链表的一部分
{
    struct Node* newNode = createNode(data);
    struct Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;
    curr->next = newNode;
}
void printList(struct Node* head)//输出链表
{
    struct Node* curr = head->next;
    while (curr != NULL)
    {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}
void mergeLists(struct Node* list1, struct Node* list2)//将两个非递减有序单链表合并成一个非递减有序单链表
{
    //========begin=======
    
    


    //=========end========
}
void freeList(struct Node* head) //释放节点所占的内存空间
{
    struct Node* curr = head;
    while (curr != NULL)
    {
        struct Node* temp = curr;
        curr = curr->next;
        free(temp);
    }
}
int main()
{
    struct Node* list1 = createNode(0);
    struct Node* list2 = createNode(0);
    int m, n, i, x;
    scanf("%d", &m); //输入第一个链表
    for (i = 0; i < m; i++)
    {
        scanf("%d", &x);
        insertNode(list1, x);
    }
    //========begin=======
    //和输入第一个单链表一样，输入第二个链表
    
    

    //=========end========
    
    mergeLists(list1, list2); //合并链表
    printList(list1);
    freeList(list1);
    freeList(list2);
    return 0;
}

从顺序表换成单链表了，逻辑一样，代码如下：


#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node* next;
};
struct Node* createNode(int data)//初始化链表
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL)
    {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void insertNode(struct Node* head, int data)//将数据加入成为链表的一部分
{
    struct Node* newNode = createNode(data);
    struct Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;
    curr->next = newNode;
}
void printList(struct Node* head)//输出链表
{
    struct Node* curr = head->next;
    while (curr != NULL)
    {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}
void mergeLists(struct Node* list1, struct Node* list2)//将两个非递减有序单链表合并成一个非递减有序单链表
{
    //========begin=======
    struct Node* p1=list1->next;
    struct Node* p2=list2->next;
    struct Node* pHead = list1;
    while(p1 && p2)
    {
        if(p1->data < p2->data)
        {
            pHead->next = p1;
            pHead = p1;
            p1 = p1->next;
        }else
        {
            pHead->next = p2;
            pHead = p2;
            p2=p2->next;
        }
    }
    while(p1)
    {
        pHead->next = p1;
        pHead = p1;
        p1 = p1->next;
    }
    while(p2)
    {
        pHead->next = p2;
        pHead = p2;
        p2 = p2->next;
    }
    pHead->next = 0;
    list2->next = 0;

    //=========end========
}
void freeList(struct Node* head) //释放节点所占的内存空间
{
    struct Node* curr = head;
    while (curr != NULL)
    {
        struct Node* temp = curr;
        curr = curr->next;
        free(temp);
    }
}
int main()
{
    struct Node* list1 = createNode(0);
    struct Node* list2 = createNode(0);
    int m, n, i, x;
    scanf("%d", &m); //输入第一个链表
    for (i = 0; i < m; i++)
    {
        scanf("%d", &x);
        insertNode(list1, x);
    }
    //========begin=======
    //和输入第一个单链表一样，输入第二个链表
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        insertNode(list2,x);
    }


    //=========end========

    mergeLists(list1, list2); //合并链表
    printList(list1);
    freeList(list1);
    freeList(list2);
    return 0;
}

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
解析：
这个问题是要求将两个非递减有序单链表合并成一个非递减有序单链表。我们可以使用双指针的方法，一个指针i指向list1的头节点，另一个指针j指向list2的头节点。然后比较两个指针所指向的节点的值，将较小的节点接在结果链表的末尾，并将对应的指针向后移动一位。重复这个过程，直到某一个指针到达链表的尾部。最后，将另一个链表剩余的部分接在结果链表的末尾。

代码如下：

void mergeLists(struct Node* list1, struct Node* list2)//将两个非递减有序单链表合并成一个非递减有序单链表
{
    struct Node* head = NULL;
    struct Node* tail = NULL;
    struct Node* i = list1;
    struct Node* j = list2;
    while (i != NULL && j != NULL)
    {
        if (i->data <= j->data)
        {
            tail->next = i;
            tail = i;
            i = i->next;
        }
        else
        {
            tail->next = j;
            tail = j;
            j = j->next;
        }
    }
    tail->next = i == NULL ? j : i;
}

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢

【以下回答由 GPT 生成】

解决方案

首先要实现链表的合并，我们可以使用迭代的方式来解决这个问题。我们需要维护两个指针，分别指向两个链表的当前节点，以及一个指向合并后链表的尾节点的指针。我们可以比较当前节点的大小，将较小的节点添加到合并后的链表中，并更新相应的指针。具体步骤如下：

创建一个新的空节点作为合并后链表的头节点，命名为mergedListHead，并用一个指针变量tail指向该节点。
使用两个指针p1和p2分别指向list1和list2的第一个节点。
比较p1->data和p2->data的值，将较小的节点添加到合并后链表的尾部，同时更新tail的指向。如果p1->data <= p2->data，将p1节点添加到tail->next，并将tail指向p1；否则，将p2节点添加到tail->next，并将tail指向p2。
随后，将p1或者p2指向其下一个节点，重复步骤3，直到其中一个链表达到末尾。
最后，将另一个链表直接拼接到合并链表的末尾，即将tail->next指向剩余链表的头部。
返回合并后的链表mergedListHead。

下面是代码实现：

void mergeLists(struct Node* list1, struct Node* list2)
{
    struct Node* mergedListHead = createNode(-1); // 创建合并链表的头节点
    struct Node* tail = mergedListHead; // 合并链表尾部的指针
    struct Node* p1 = list1->next; // list1的当前节点
    struct Node* p2 = list2->next; // list2的当前节点

    // 遍历两个链表
    while (p1 != NULL && p2 != NULL)
    {
        // 将较小的节点添加到合并链表的尾部，并更新tail指针
        if (p1->data <= p2->data)
        {
            tail->next = p1;
            p1 = p1->next;
        }
        else
        {
            tail->next = p2;
            p2 = p2->next;
        }
        tail = tail->next;
    }

    // 将剩余节点直接拼接到合并链表的末尾
    if (p1 != NULL)
    {
        tail->next = p1;
    }
    else if (p2 != NULL)
    {
        tail->next = p2;
    }

    // 打印合并后的链表
    printList(mergedListHead);

    // 释放合并链表内存
    freeList(mergedListHead);
}

完整代码如下：

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

struct Node
{
    int data;
    struct Node* next;
};

struct Node* createNode(int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL)
    {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertNode(struct Node* head, int data)
{
    struct Node* newNode = createNode(data);
    struct Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;
    curr->next = newNode;
}

void printList(struct Node* head)
{
    struct Node* curr = head->next;
    while (curr != NULL)
    {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

void mergeLists(struct Node* list1, struct Node* list2)
{
    struct Node* mergedListHead = createNode(-1); // 创建合并链表的头节点
    struct Node* tail = mergedListHead; // 合并链表尾部的指针
    struct Node* p1 = list1->next; // list1的当前节点
    struct Node* p2 = list2->next; // list2的当前节点

    // 遍历两个链表
    while (p1 != NULL && p2 != NULL)
    {
        // 将较小的节点添加到合并链表的尾部，并更新tail指针
        if (p1->data <= p2->data)
        {
            tail->next = p1;
            p1 = p1->next;
        }
        else
        {
            tail->next = p2;
            p2 = p2->next;
        }
        tail = tail->next;
    }

    // 将剩余节点直接拼接到合并链表的末尾
    if (p1 != NULL)
    {
        tail->next = p1;
    }
    else if (p2 != NULL)
    {
        tail->next = p2;
    }

    // 打印合并后的链表
    printList(mergedListHead);

    // 释放合并链表内存
    freeList(mergedListHead);
}

void freeList(struct Node* head)
{
    struct Node* curr = head;
    while (head != NULL)
    {
        curr = head;
        head = head->next;
        free(curr);
    }
}

int main()
{
    struct Node* list1 = createNode(-1); // 使用-1作为第一个节点的data值
    struct Node* list2 = createNode(-1); // 使用-1作为第一个节点的data值

    int n1, n2, num;
    scanf("%d", &n1); // 读取第一个链表的节点数
    for (int i = 0; i < n1; i++)
    {
        scanf("%d", &num); // 读取节点值
        insertNode(list1, num);
    }

    scanf("%d", &n2); //读取第二个链表的节点数
    for (int i = 0; i < n2; i++)
    {
        scanf("%d", &num); // 读取节点值
        insertNode(list2, num);
    }

    mergeLists(list1, list2); // 合并链表

    freeList(list1); // 释放链表内存
    freeList(list2); // 释放链表内存

    return 0;
}

测试样例的运行结果为：1 2 3 3 4 5 6 7 8 9 10。

【相关推荐】

帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7690114
这篇博客也不错, 你可以看下实现输入10个数，输出这10个数的和，平均值；输出该组数中数与数的最大差值；将数组元素逆置（例如数组1、2、3、4交换位置输出4、3、2、1）。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632