已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。 要求S3中没有重复元素。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出合并后新的非降序链表，要求链表中没有重复元素。数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。 输入样例: 在这里给出一组输入。例如： 1 3 3 5 8 -1 2 3 4 6 8 10 -1 输出样例: 在这里给出相应的输出。例如： 1 2 3 4 5 6 8 10C语言代码

### 合并两个有序链表为无重复值的升序链表 以下是基于提供的引用内容以及专业知识编写的 C 语言代码，用于将两个非降序链表合并成一个新的不包含重复值的升序链表。 #### 定义链表节点结构 首先定义链表节点的数据结构 `struct ListNode`，其中包含一个整数值域 `val` 和指向下一个节点的指针 `next`。 ```c #include <stdio.h> #include <stdlib> // 定义链表节点结构体 typedef struct ListNode { int val; struct ListNode* next; } ListNode; // 创建新节点函数 ListNode* createNode(int value) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); if (!newNode) { printf("内存分配失败\n"); exit(1); } newNode->val = value; newNode->next = NULL; return newNode; } ``` #### 输入链表构建逻辑 通过用户输入的方式动态创建两个初始的有序单链表。为了简化操作，可以假设输入已经按照递增顺序排列。 ```c // 构建链表函数 ListNode* buildList() { int n, temp; scanf("%d", &n); // 输入链表长度 if (n == 0) return NULL; // 如果长度为零，则返回空列表 ListNode *head = NULL, *tail = NULL; while (n--) { // 循环读入数据 scanf("%d", &temp); ListNode* newNode = createNode(temp); if (!head) head = tail = newNode; // 初始化头部和尾部 else { tail->next = newNode; tail = newNode; } } return head; } ``` #### 主要功能：去重合并两链表 利用双指针法遍历两条链表，并在过程中移除重复项。最终生成一条全新的、不含任何重复元素的升序链表。 ```c // 合并不含重复元素的升序链表 ListNode* mergeUniqueLists(ListNode* list1, ListNode* list2) { ListNode guard = { .val = 0, .next = NULL }; // 使用哨兵节点简化边界情况处理 ListNode* current = &guard; while (list1 && list2) { if (list1->val < list2->val) { if (!current->next || list1->val != current->next->val) { // 检查是否有相同值已存在 current->next = createNode(list1->val); current = current->next; } list1 = list1->next; } else if (list1->val > list2->val){ if (!current->next || list2->val != current->next->val) { // 检查是否有相同值已存在 current->next = createNode(list2->val); current = current->next; } list2 = list2->next; } else { // 当两者相等时只加入其中一个 if (!current->next || list1->val != current->next->val) { // 确保不会插入重复值 current->next = createNode(list1->val); current = current->next; } list1 = list1->next; list2 = list2->next; } } // 处理剩余部分 while (list1) { if (!current->next || list1->val != current->next->val) { // 继续检查重复值 current->next = createNode(list1->val); current = current->next; } list1 = list1->next; } while (list2) { if (!current->next || list2->val != current->next->val) { // 继续检查重复值 current->next = createNode(list2->val); current = current->next; } list2 = list2->next; } return guard.next; // 返回真正的头节点 } // 打印链表函数 void printList(ListNode* head) { while (head) { printf("%d ", head->val); head = head->next; } printf("\n"); } ``` #### 测试与验证 提供完整的测试框架来演示上述算法的功能。 ```c int main() { printf("请输入第一个链表的元素数量及其具体值:\n"); ListNode* list1 = buildList(); printf("请输入第二个链表的元素数量及其具体值:\n"); ListNode* list2 = buildList(); printf("原始链表一:"); printList(list1); printf("原始链表二:"); printList(list2); ListNode* mergedList = mergeUniqueLists(list1, list2); printf("合并后的无重复升序链表:"); printList(mergedList); return 0; } ``` 以上实现了从输入到输出整个流程的设计[^1][^3]。值得注意的是，在实际应用中还需要考虑更多异常场景下的健壮性设计，比如极端大小或者负数等情况。