已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。c语言

在C语言中，要设计一个函数来构建两个非降序链表S1和S2的交集链表S3，可以采用以下步骤：

1. 定义结构体`ListNode`表示链表节点，包含数据域`data`和指针域`next`。

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

2. 创建一个辅助函数`isInList`，用于检查一个元素是否在给定链表中。

bool isInList(ListNode* list, int target) {
    while (list != NULL) {
        if (list->data == target)
            return true;
        list = list->next;
    }
    return false;
}

3. 主函数`mergeLists`中，初始化一个空链表`result`作为结果，并遍历第一个链表S1。

ListNode* mergeLists(ListNode* S1, ListNode* S2) {
    ListNode* result = NULL; // 新链表头结点
    ListNode* current1 = S1;
    ListNode* current2 = S2;

    // 遍历S1
    while (current1 != NULL && current2 != NULL) {
        if (current1->data < current2->data) {
            // 如果S1的当前元素不在S2中，则添加到结果
            if (!isInList(current2, current1->data)) {
                if (result == NULL)
                    result = current1;
                else
                    result->next = current1;
                current1 = current1->next;
            } else { // S1的当前元素也在S2中，跳过
                current1 = current1->next;
            }
        } else { // 相同或S2的当前元素小于S1
            if (!isInList(current1, current2->data)) {
                if (result == NULL)
                    result = current2;
                else
                    result->next = current2;
                current2 = current2->next;
            } else { // S2的当前元素也在S1，跳过
                current2 = current2->next;
            }
        }
    }

    // 将剩余部分添加至结果链表
    while (current1 != NULL || current2 != NULL) {
        if (current1 != NULL)
            result->next = current1, current1 = current1->next;
        else
            result->next = current2, current2 = current2->next;
    }

    return result;
}