合并两个有序链表序列

"合并两个有序链表" 在计算机科学中，数据结构是组织和存储数据以便高效地访问和管理的方式。链表是一种基本的数据结构，其中元素不是在内存中的连续位置，而是通过指针链接。在这个问题中，我们讨论的是如何合并两个已排序的链表以创建一个新的有序链表。 题目描述了一个典型的链表操作问题，要求将两个非降序（升序）链表S1和S2合并成一个新的非降序链表S3。链表的元素是正整数，以-1作为序列的结束标记。输入样例给出了两个这样的链表，输出样例展示了合并后的结果。 首先，我们需要了解链表的基本结构。在C语言中，一个链表节点通常由数据部分和指向下一个节点的指针组成。在给定的代码中，定义了`Node`结构体来表示链表节点： ```c typedef struct Node { int data; struct Node* next; } Node, *Linklist; ``` `Linklist`是一个指向`Node`结构体的指针，方便我们操作链表。 接下来，代码定义了几个关键函数： 1. `CreatList(Linklist *L)`：此函数用于创建一个带头结点的单链表。它使用尾插法构建链表，即新节点总是添加到链表的末尾。当读取到-1时，表示序列结束，停止输入。 2. `ListMerge(Linklist L1, Linklist L2)`：这是主要的合并函数，接收两个已排序的链表作为参数，返回合并后的链表。它创建了一个新的链表`L3`，然后比较`L1`和`L2`当前节点的值，将较小的节点添加到`L3`，并移动相应的指针。如果一个链表为空，就将另一个链表的剩余部分追加到`L3`。 3. `Print(Linklist L)`：这是一个简单的打印链表的函数，遍历链表并打印每个节点的`data`。 在`main()`函数中，创建了两个链表`L1`和`L2`，然后调用`ListMerge`合并它们，并打印结果。 链表合并的时间复杂度为O(m + n)，其中m和n分别是两个输入链表的长度。这是因为我们需要遍历两个链表一次。空间复杂度为O(1)，因为我们只使用了常数级别的额外空间。 总结来说，解决这个问题的关键在于理解链表的结构和操作，以及如何在已排序链表之间进行有效的比较和合并。这个练习有助于提升对链表操作和合并算法的理解，这对于处理涉及链表数据结构的实际问题至关重要。