【C语言】合并链表问题

Question

问题描述：
题目：两个非降序链表的并集，例如将链表1->2->3 和 2->3->5 并为 1->2->3->5，只能输出结果，不能修改两个链表的数据。
【输入形式】
第一行为第一个链表的各结点值，以空格分隔。
第二行为第二个链表的各结点值，以空格分隔。
【输出形式】
合并好的链表，以非降序排列，值与值之间以空格分隔。
【样例输入】
4 7 10 34
1 4 6 29 34 34 52
【样例输出】
1 4 6 7 10 29 34 52

我的代码实现如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

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

LTNode* BuySLTNode(SLTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

LTNode* CreateSList()
{
    SLTDataType data;
    LTNode* phead = NULL, * ptail = NULL;
    while (scanf("%d",&data)!=EOF)
    {
        LTNode* newnode = BuySLTNode(data);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
        if (getchar() == '\n')
        {
            break;
        }
    }
    return phead;
}

void LTPrint(LTNode* phead)
{
    LTNode* cur = phead;
    while (cur)
    {
        printf("%d ", cur->val);
        cur = cur->next;
    }
}

LTNode* MergeTwoLists(LTNode* list1, LTNode* list2)
{
    LTNode* guard, *tail;
    guard = tail = (LTNode*)malloc(sizeof(LTNode));
    while (list1&&list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else if (list1->val > list2->val)
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
        else
        {
            if (tail->val != list2->val)
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
            list1 = list1->next;
        }
    }
    while(list1)
    {
        if (tail->val != list1->val)
        {
            tail->next = list1;
            list1 = list1->next;
            tail = tail->next;
            continue;
        }
        list1 = list1->next;
    }
    while(list2)
    {
        if (tail->val != list2->val)
        {
            tail->next = list2;
            list2 = list2->next;
            tail = tail->next;
            continue;
        }
        list2 = list2->next;
    }
        
    LTNode* newhead = guard->next;
    free(guard);
    return newhead;
}

int main()
{
    LTNode* plist1 = CreateSList();
    LTNode* plist2 = CreateSList();
    LTNode* plist3 = MergeTwoLists(plist1, plist2);
    LTPrint(plist3);
    return 0;
}

• 我的思路：同时遍历两个链表，值更小的插入到新链表

• 我的疑惑：不知道该如何处理值的重复出现
  如：
  

  

希望得到解答 ，非常感谢！

Answer 1

不要只判断链表A和B谁大，顺便判断一下和C相等不相等，相等就过
其实就是执行插入之前先判断一下不相等再插入，相等就什么都不做，继续循环

Answer 2

LTNode* MergeTwoLists(LTNode* list1, LTNode* list2)
{
    LTNode guard = { 0 }, *tail = &guard;
    list1 = sortList(list1);
    list2 = sortList(list2);
    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else if (list1->val > list2->val) {
            tail->next = list2;
            list2 = list2->next;
        } else {
            LTNode* tmp = list1;
            list1 = list1->next;
            free(tmp);
        }
        tail = tail->next;
    }

    tail->next = list1 ? list1 : list2;
    LTNode* newhead = guard.next;
    return newhead;
}

Answer 3

• 这篇文章：【C语言练习】字符串合并排序 也许有你想要的答案，你可以看看