合并升序链表的C语言实现

在IT领域，特别是在数据结构和算法中，处理链表的问题是非常常见的，特别是当涉及到对有序链表的操作时。本文档主要讨论的是如何合并两个已排序的链表（升序链表）L1和L2，形成一个新的升序链表L。这个过程可以通过迭代的方式来实现，下面是对该问题的详细解释和C语言代码实现。 首先，合并两个有序链表的关键在于比较当前节点的值，根据值的大小决定将哪个节点的数据添加到新链表L中。在这个过程中，我们创建了一个辅助链表L，并使用两个指针p和q分别指向L1和L2的头节点。初始时，L、p和q都是空或指向头节点。 1. **初始化**: - 初始化新链表L，将其头节点设置为NULL。 - 定义两个临时指针L1_head和L2_head，分别记录原始链表L1和L2的头节点，便于在合并过程中跟踪链表的起始位置。 - 创建整型变量p1和q1，用于计数当前遍历的节点数量，以便在必要时检查是否达到链表末尾。 2. **遍历和合并**: - 当p和q都不为空时，进入循环： - 检查p所指向的节点值是否小于等于q所指向的节点值。如果是，将p的值插入新链表L，更新L的新节点为head，然后将p向前移动一个节点。 - 更新p1计数器，当达到链表长度的整数倍时，表示p已经到达L1的末尾，跳出内层循环。 - 类似地，如果p的值大于q的值，则将q的值插入新链表L，更新q并继续。 - 在每次循环后，将p和q分别移动到下一个节点，直至其中一个为空。 3. **处理剩余节点**: - 当p或q中的一个为空时，将另一个链表的剩余部分（L1或L2）连接到新链表L的末尾。这取决于哪个链表还有剩余节点，即p1和q1的大小关系。 4. **返回结果**: - 返回合并后的链表L的头节点。 提供的C语言代码实现了上述步骤，通过`Merge()`函数接收两个有序链表L1和L2的头节点作为参数，返回合并后的链表头节点。需要注意的是，代码假定输入链表已经按照升序排列，如果没有排序，需先进行排序操作。同时，它依赖于预先定义好的`structNode`结构体，包含`Data`和`Next`成员变量。 这个算法的时间复杂度是O(m + n)，其中m和n分别是两个链表的长度，因为它最多会遍历两个链表各一次。空间复杂度为O(1)，因为仅用到了几个额外的指针变量，没有使用与输入链表长度相关的额外空间。