c语言实现两个单链表交叉合并

要实现两个单链表的交叉合并，可以按照以下步骤进行：

1. 首先定义一个新的单链表，用于存储合并后的结果。

2. 然后定义两个指针，分别指向两个输入的单链表的头节点。

3. 使用循环来遍历两个单链表，比较当前节点的值大小。

4. 如果第一个链表的当前节点的值小于等于第二个链表的当前节点的值，就将第一个链表的当前节点插入到新链表的末尾，并将第一个链表的指针指向下一个节点。

5. 反之，如果第二个链表的当前节点的值小于第一个链表的当前节点的值，就将第二个链表的当前节点插入到新链表的末尾，并将第二个链表的指针指向下一个节点。

6. 循环直到其中一个链表遍历完。

7. 如果其中一个链表已经遍历完，将未遍历完的链表的剩余节点直接插入到新链表的末尾。

8. 返回合并后的新链表。

以下是一个示例代码，实现了上述的逻辑：

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

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

Node* mergeLists(Node* head1, Node* head2) {
    Node* dummy = (Node*)malloc(sizeof(Node));
    Node* tail = dummy;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            tail->next = head1;
            head1 = head1->next;
        } else {
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next;
    }

    if (head1 != NULL) {
        tail->next = head1;
    }
    if (head2 != NULL) {
        tail->next = head2;
    }

    Node* mergedList = dummy->next;
    free(dummy);

    return mergedList;
}

int main() {
    // 创建第一个链表
    Node* head1 = (Node*)malloc(sizeof(Node));
    head1->data = 1;
    head1->next = (Node*)malloc(sizeof(Node));
    head1->next->data = 3;
    head1->next->next = (Node*)malloc(sizeof(Node));
    head1->next->next->data = 5;
    head1->next->next->next = NULL;

    // 创建第二个链表
    Node* head2 = (Node*)malloc(sizeof(Node));
    head2->data = 2;
    head2->next = (Node*)malloc(sizeof(Node));
    head2->next->data = 4;
    head2->next->next = (Node*)malloc(sizeof(Node));
    head2->next->next->data = 6;
    head2->next->next->next = NULL;

    // 合并链表
    Node* mergedList = mergeLists(head1, head2);

    // 打印合并后的结果
    while (mergedList != NULL) {
        printf("%d ", mergedList->data);
        mergedList = mergedList->next;
    }

    return 0;
}

以上代码中定义了一个`mergeLists`函数，用于合并两个单链表。在代码的`main`函数中，创建了两个示例链表，并调用`mergeLists`函数进行了合并，最后打印出合并后的结果。