c++单向链表排序（c++单链表逆序）



原文链接：https://ethsonliu.com/2019/08...

单链表经常为公司面试所提及，先不贬其过于简单，因为单链表确实是数据结构中最简单的一部分，但往往最简单的，人们越无法把握其细节。本文一共总结了单链表常被提及的各种操作，如下：

1. 逆序构造单链表；
2. 链表反转；
3. 链表排序；
4. 合并两个有序链表；
5. 求出链表倒数第k个值；
6. 判断链表是否有环，有环返回相遇结点；
7. 在一个有环链表中找到环的入口；
8. 删除当前结点；
9. 找出链表的中间结点。

本文中的所有操作均针对带有头结点的单链表。请注意：头结点和第一结点是两个结点，百度百科解释为：为方便操作，在单链表的第一个结点之前附设一个结点，称之为头结点。本文中用header代替头结点。

在继续下文之前先约定下结点结构：

例如：输入数据：1 2 3 4 5 6，构造单链表：6->5->4->3->2->1。

例如：假设现有链表：6->5->4->3->2->1，进行反转操作后，链表变成：1->2->3->4->5->6。

我们希望用最小的时间复杂度来完成这个排序任务。归并排序是个不错的选择，平均时间复杂度$T(n)=O(nlogn)$，但是还有其他方法么？

我们想到经常出现的快排，快排是需要一个指针指向头，一个指针指向尾，然后两个指针相向运动并按一定规律交换值，最后使得支点左边小于支点，支点右边大于支点，但是对于单链表而言，指向结尾的指针很好办，但是这个指针如何往前，我们只有一个next（这并不是一个双向链表）。

如果是这样的话，对于单链表我们没有前驱指针，怎么能使得后面的那个指针往前移动呢？所以这种快排思路行不通，如果我们能使两个指针都往next方向移动并且也可以按相同规律交换值那就好了，怎么做呢？

接下来我们使用快排的另一种思路来解答。我们只需要两个指针i和j，这两个指针均往next方向移动，移动的过程中始终保持区间[1, i]的data都小于base（位置0是主元），区间[i+1, j)的data都大于等于base，那么当j走到末尾的时候便完成了一次支点的寻找。若以swap操作即if判断语句成立作为基本操作，其操作数和快速排序相同，故该方法的平均时间复杂度亦为$T(n)=O(nlogn)$。

为简化问题，以下代码为合并两个升序链表。

例如，给定链表1->4->3->5->6->8，返回倒数第3个数，也就是5。要求，只给定链表，但并不知道链表长度，如何在最短时间内找出这个倒数第k个值。

其实思路很简单，假设k是小于等于链表长度，那么我们可以设置两个指针p和q，这两个指针在链表里的距离就是k，那么后面那个指针走到链表末尾的nullptr时，另一个指针肯定指向链表倒数第k个值。

有环是什么意思？一个单链表最后一个结点的位置的next应该是nullptr，标志着链表的结尾，但是如果现在这个next指向了链表里的某一个结点（可以是自身），那么这个链表就存在环。如下图：

因此我们只要找到两个结点，其地址相同（因为两个结点的data可能相同），即可断定有环。

我们的思路就是：设置两个快慢指针（快慢指针即两个指针起点相同，慢指针每次走一步，快指针走两步），让它们一直往下走，直到它们相等，说明有环；遇到nullptr，说明无环。下面简单证明：如上图，A为链表第一个结点，B为环与链表的交叉点，C为与相遇的位置。假设环的长度为r，则有

$$ AB+BC+t_1r=frac {AB+BC+t_2r}{2} ag{左为慢指针，右为快指针} $$

化简为：

$$ AB+BC=(t_2-2t_1)r ag{t1,t2为整数} $$

在确定了AB和r后，只需调整BC，使AB+BC能整除r即可。

参考2.6图，若存在环且找到了相遇点C，此时令一个指针start_node从链表第一个结点处开始往后遍历，再令另一个指针meet_node从C处往后遍历，它们的相遇结点就是环的入口点。为什么呢？

2.6公式已经证明了：若快慢指针相遇在C点，则：

$$ AB+BC=tr ag{t是整数} $$

进一步整理上式为：

$$ AB=(r-BC)+(t-1)r ag{其中r-BC的含义请对照2.6图} $$

好了，至此，证明就已经很显然了。当start_node走了r-BC距离后，meet_node正好到达入口处B点，此时start_node还剩(t-1)r距离，显然两个指针继续走的话，一定会相遇在入口处B点。

此外，我们也会遇到“判断两个链表是否相交”，“求出两个相交链表的交点”这样的问题，百变不离其宗，我们只需把链表尾接到其中一个链表头就转化为2.6和2.7的问题，所以在这里不作详述了。

题意规定，给定要删除的结点和头结点，现要你删除这个结点，要求平均时间复杂度为$T(n)=O(1)$。

例如，现有这样的链表，1->2->3->4->5->6，需要删除4，我们的思路肯定是先找到4的前一个结点3，和4的后一个结点5，然后把3和5连起来，再把4删除。但是这样做的话，我们需要花费$O(n)$的时间来找到3和5，与题意要求的$O(1)$相距甚远。

我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除结点的前一个结点。我们试着换一种思路。如果我们要删除4，可以把4和5的数据交换下，然后删除5，再把4和6连接起来，如此其时间复杂度为$O(1)$。

上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是$O(n)$。那题目要求我们需要在$O(1)$时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1个情况下，时间复杂度是$O(1)$，只有当给定的结点处于链表末尾的时候，时间复杂度为$O(n)$。因此其平均时间复杂度$frac {(n-1)⋅O(1)+1⋅O(n)}n$，仍然为$O(1)$。

上面的思路似乎不太令人满意。我们又想到快慢指针，它有一个很重要的性质：慢指针走的长度等于快慢指针相距的程度。所以利用这个性质，当快指针走到链表尾时，慢指针正好在中间结点。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/13042.html