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

如下所示： #include<stdio> #include<stdlib> #include<iostream> using namespace std; struct Node { int data; Node *next; }; //初始化 Node *init() { Node *head=new Node; head->next=NULL; return head; } //头插法创建节点 void insetList(Node *head,int i) { Node *cur=new Node; cur->data=i; cur->next=head->n 在本文中，我们将深入探讨如何使用C语言实现两个单链表的交叉合并。单链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。交叉合并是指将两个已排序的单链表交错地连接在一起，形成一个新的有序链表。 我们定义一个名为`Node`的结构体，它包含一个整型数据成员`data`和一个指向下一个节点的指针`next`。结构体的定义如下： ```cpp struct Node { int data; Node *next; }; ``` 接下来，我们需要一些辅助函数来操作链表。`init()`函数用于初始化一个新的空链表，返回链表的头指针。`insetList()`函数采用头插法创建新的节点并将其插入到链表的头部。 ```cpp // 初始化链表 Node *init() { Node *head = new Node; head->next = NULL; return head; } // 头插法创建节点 void insetList(Node *head, int i) { Node *cur = new Node; cur->data = i; cur->next = head->next; head->next = cur; } ``` 为了演示交叉合并，我们创建两个链表`head_A`和`head_B`。`CreateList()`函数负责生成这两个链表，并确保它们具有相同的长度，但元素交错排列。例如，如果链表A的元素是1, 3, 5, ...，链表B的元素则是2, 4, 6, ...。 ```cpp // 创建链表A, B void CreateList(Node *head_A, Node *head_B) { for (int i = 0; i < 20; i++) { insetList(head_A, i); i++; // 跳过一个元素以交错插入 insetList(head_B, i); } // 增加链表B的长度 insetList(head_B, 20); insetList(head_B, 25); } ``` 关键的合并操作在`Linklist()`函数中完成。该函数接受两个链表的头指针`head_A`和`head_B`以及一个新链表`List_C`的头指针。它通过两个指针`pa`和`pb`分别遍历链表A和B，同时使用`pc`指针在新链表C中创建节点。当其中一个链表遍历结束时，剩余的节点将被附加到新链表的末尾。 ```cpp // 交叉合并链表 void Linklist(Node *head_A, Node *head_B, Node *List_C) { Node *pa = head_A->next; // pa指向链表A的首元节点 Node *pb = head_B->next; // pb指向链表B的首元节点 Node *pc = List_C; // pc指向C的头节点 while (pa && pb) { // 某一链表遍历结束即退出 pc->next = pa; // 先存A链表的节点 pc = pa; // pc指向pa，pc前进一个节点 pa = pa->next; // pa前进一个节点 pc->next = pb; // 存B链表的节点 pc = pb; pb = pb->next; } // 判断谁先结束，然后把没结束的剩余结点的链接上 pc->next = pa ? pa : pb; delete head_B; // 释放链表B } ``` 我们提供一个`print()`函数用于打印链表的元素，以及一个`main()`函数来演示整个流程。`main()`函数创建链表A和B，打印它们，然后调用`Linklist()`函数合并这两个链表，并输出合并后的链表C。 总结：在处理链表时，确保不要随意更改头指针的位置，以免破坏链表结构。在进行合并时，使用额外的指针变量可以简化操作。此外，当一个链表遍历完成后，记得正确处理另一个链表的剩余部分。在本例中，由于我们创建了一个新的链表C，因此在合并后释放了原始链表B的内存。了解这些基本操作对于理解和实现更复杂的链表算法至关重要。