C语言求两有序链表的并集

可以用归并排序的思想来实现有序链表的并集，具体步骤如下：

1.定义两个指针p和q，分别指向两个有序链表的头结点；

2.新建一个链表result，用于存放两个链表的并集；

3.比较p和q指向的结点的值，将较小的值加入result链表中，并将指向该结点的指针后移一位；

4.重复步骤3，直到其中一个链表遍历完毕；

5.将另一个链表剩余的结点依次加入result链表中；

6.返回result链表的头结点。

下面是C语言的实现代码：

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

// 定义链表结构体
typedef struct node {
    int data;
    struct node* next;
} Node, *LinkList;

// 创建链表
LinkList createList(int n) {
    LinkList head, p, q;
    head = (LinkList)malloc(sizeof(Node));
    head->next = NULL;
    p = head;
    printf("请输入%d个有序链表的值：\n", n);
    for (int i = 0; i < n; i++) {
        q = (LinkList)malloc(sizeof(Node));
        scanf("%d", &q->data);
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return head;
}

// 遍历链表
void traverseList(LinkList head) {
    Node* p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 合并两个有序链表
LinkList mergeList(LinkList L1, LinkList L2) {
    Node* p = L1->next, * q = L2->next;
    LinkList head, r, s;
    head = (LinkList)malloc(sizeof(Node));
    head->next = NULL;
    r = head;
    while (p && q) {
        if (p->data <= q->data) {
            s = (LinkList)malloc(sizeof(Node));
            s->data = p->data;
            r->next = s;
            r = s;
            p = p->next;
        }
        else {
            s = (LinkList)malloc(sizeof(Node));
            s->data = q->data;
            r->next = s;
            r = s;
            q = q->next;
        }
    }
    while (p) {
        s = (LinkList)malloc(sizeof(Node));
        s->data = p->data;
        r->next = s;
        r = s;
        p = p->next;
    }
    while (q) {
        s = (LinkList)malloc(sizeof(Node));
        s->data = q->data;
        r->next = s;
        r = s;
        q = q->next;
    }
    r->next = NULL;
    return head;
}

int main() {
    int n1, n2;
    LinkList L1, L2, L;
    printf("请输入第一个有序链表的长度：");
    scanf("%d", &n1);
    L1 = createList(n1);
    printf("第一个有序链表为：");
    traverseList(L1);
    printf("请输入第二个有序链表的长度：");
    scanf("%d", &n2);
    L2 = createList(n2);
    printf("第二个有序链表为：");
    traverseList(L2);
    L = mergeList(L1, L2);
    printf("合并后的有序链表为：");
    traverseList(L);
    return 0;
}

希望能够帮助到你！