如何合并排序链表

1.概述

在本教程中，我们将讨论使用合并排序算法对链表排序。

首先，我们将定义这个问题并提供一个示例来解释它。

其次，我们将讨论解决这个问题的两种方法。

2.定义问题

假设我们有一个链表由多个节点组成，每个节点存储两个值：

1. ：它表示存储在节点中的值。
2. ：它表示到列表中当前节点后的下一个节点的指针。

我们的任务是使用合并排序算法对这个链表进行排序，使链表的每个节点的值都大于之前所有节点的值。

让我们来检查一个例子以便更好地理解。假设我们有以下链接列表：

对给定的链接列表进行排序后，我们将获取以下链接列表：

正如我们所看到的，每个节点的值都大于前面所有节点的值。

3.递归方法

3.1。大意

在这种方法中，我们将通过制作将给定的链接列表拆分为两半列表中间节点的值等于，然后分别对每一半调用递归排序函数，在每次调用结束时，我们将合并两个已排序的一半，以使链表排序。

3．2．执行

我们将把我们的实施划分为三个功能。首先，我们将实现一个返回列表中的中间元素的函数。接下来，我们会看到谁合并两个排序的列表。最后，我们将解释完整的算法。

３．３．获取链表的中间

让我们来看看这样的实现：

这函数将返回链接列表的中间节点。

我们定义了两个指针，慢速快速。每次，慢点指针向前移动一步，并且快速移动两个步骤前进。因此，快速指针将移动两倍慢指针所做的距离，这意味着快速指针到达链接列表的末尾时，速度将位于链接列表的中间。

3.4。合并两个排序链接列表

让我们来看看这样的实现：

这函数将两个排序列表合并为一个排序链表。

首先，我们声明了一个链表和，这是指向末尾的指针。

下一步，当当前指针和不等于我们必须维持两种情况：

1. ：这意味着当前节点列表应该在节点之前去列表，因为它具有小于或等于值的值节点。因此，这是应该是目前的节点，然后我们移动指向下一个节点的指针。
2. ：然后应该是目前的节点，然后我们移动指向下一个节点的指针。

在此之后，我们将添加到的。

当其中一个指针到达其列表的结尾时，我们会突破循环。然后，我们检查一个指针是否仍然不等于，我们将其余名单附加到结尾。

最后，我们会回来的，它是合并列表的头指针。

3.5。合并排序链接列表

让我们来看看这样的实现：

这函数将使用合并排序算法对链表进行排序。

首先，我们检查是否=，然后列表是空的。同样，如果=，这意味着在给定列表中只有一个节点。在这两种情况下，列表的排序版本仍然与初始版本相同，因此返回。

接下来，我们将使用列表的中间节点使用函数。然后，我们将把给定的列表分成两部分:

1. ：它开始了指针。
2. ：在中间节点之后开始。

之后，我们会制作等于将列表从中间节点切成两半。

最终，我们分别对每个部件进行排序，然后我们将它们合并它们以获取单个排序列表。

3.6。复杂性

这里的时间和空间复杂性是。让我们检查这种复杂性背后的原因。

首先,函数具有复杂性原因我们最多一次迭代列表的每个节点，在哪里是列表的长度。

第二，函数具有复杂性因为我们最多遍历每个列表的节点一次，其中第一个列表的长度是多少第二个的长度。

最后，函数具有复杂性导致每个呼叫中​​，我们合并两个列表，具有复杂性并且递归树的深度将是因为在每个电话中，我们将列表分成两半，在哪里是列表的长度。

这意味着总复杂性是。

4.迭代方法

4．1.大意

在这种方法中，我们将把给定的链接列表划分为两个的大小功率的排序块，然后我们将每两个连续块合并在一起。

首先，我们将列表划分为大小的块，然后我们将每两个连续块合并在一起，因此我们得到大小的块。

其次，我们将列表划分为大小的块，然后我们将每两个连续块合并在一起，因此我们得到了四大块排序。

我们继续执行这些步骤，直到块的大小达到2的1次幂，大于或等于给定链表的长度，此时，链表将被排序。

4.2。执行

我们将把我们的实施划分为两种功能。第一个负责合并两个块，而第二个是完整的算法本身。

4.3。合并两个街区

让我们来看看这样的实现：

这函数将合并两个特定大小的排序块。这个函数的形参是指向第一个块的开始和它的大小的指针。此外，对第二个块也传递相同的信息。最后，传递链表还有一个指向它末端的指针。

只要其中一个块不为空，就意味着这些块中仍然存在一些未译表的节点，因此我们执行多个步骤。

首先，我们宣布，它将存储应在列表中的最后一个节点之后的节点存储节点。

其次，我们称之为功能检查是否块是空的，或者仍然存在一些未译表的节点块。另外，它检查当前值是否为节点小于或等于当前节点的值节点，意思是节点应该在一。

如果是，则将节点到减小尺寸块一个，并移动指向下一个节点的指针。否则，这是将是一个;我们减小块一个，并移动指向下一个节点的指针。

最后,我们使等于将节点从块中删除，并将其附加到链表的末尾。

4.4。合并排序链接列表

让我们来看看这样的实现：

最初，我们宣布它表示划分后列表的每个块的大小，以及表示每两个连续的块合并后合并的块数。

接下来，只要没有达到大于或等于给定链表长度的2的第1次幂，就必须执行以下步骤:

1. 重置值为零。
2. 声明最初指向链表开头的左指针和右指针。
3. 清除列表。
4. 虽然左块大小小于和指针没有到达列表的末尾，我们移动指向列表的下一个节点的指针，并将左侧块的大小增加1。现在,信息在第一个块的开始和指针位于第二个块的开头。
5. 合并第一个和第二个区块。
6. 制作自合并后指向第二个块后面的块的开始的指针。
7. 重复所有这些步骤，直到合并整个列表，这意味着链表已排序。

4．5.复杂性

这里的空间复杂性由于我们修改了相同的列表并没有创建任何其他列表。让我们检查这种复杂性背后的原因。

关于时间复杂性，我们将给定链接列表划分为块次，直到我们达到两个大于或等于的第一倍链接列表的长度。接下来，在每次迭代中，我们将每两个连续块合并其长度总数等于的总和等于。

这意味着总复杂性是。

5.结论

在本教程中，我们介绍了使用合并排序算法对链接列表进行排序的问题。我们解释了一般的想法，并讨论了解决方法的两种方法。