单项链表查找、相交或成环的几个算法

文章目录

这篇文章介绍了单项链表上有关相交和成环的几个问题和算法。

你也可以参考有关单项链表的另外几篇文章:

单项链表实现的栈

反转单项链表的四种算法

判断两个单项链表是否相交

问题描述

给定两个单向链表,判断链表是否相交(有共同的节点)。

算法一

最直接的解法,就是对其中一个链表(链表一)进行遍历,在遍历到每一个节点时,都在另一个链表(链表二)中进行遍历,看是否有重复的节点,假设两个链表的长度分别是 n 和 m,那么最坏的渐进时间复杂度为 O (n * m)。

算法一的改进

凡是检索节点均可能进行改进。算法一中存在对链表二的多次扫描检索,可以采取以下思路进行简化:

  • 以空间换时间:使用标记数组将链表二中存在的值进行标记,然后遍历链表一的时候,直接使用O (1) 的方法判断是否在于链表二中。但这要求链表二的内容取值范围较少或空间较大。简化后,时间复杂度变为 O(n + m),但空间复杂度较高。
  • 将链表二的内容排序,利用二分查找减少查找时间,将空间复杂度降低为 O(nlog[2](m))。

注意:这里所谓的「改进」有一个前提:节点的值不能重复。也就是说,重复节点值必须能够代表同一个节点。

算法二

算法二的思路基于以下两个原理:

  • 两个单向链表相交后,必然无法再分开。这是很容易想到的,因为只有一个方向,一旦有相同的节点,那么后续的节点一定相同。
  • 两个单项链表相交后,尾节点一定相同。基于第一个原理,容易想到第二个。

于是,我们给出这样的判断:两个链表相交,当且仅当两个链表的尾元素相同:

  1. 假设两个链表相交,很容易证明两个链表的尾元素是相同的。
  2. 逆反命题:两个链表的尾元素相同时,两个链表一定相交。(注意:相同的节点不仅仅要求值相同,而是「同一个」,也就是指针地址相同。)

算法思路如下:

  1. 遍历链表一,找出尾节点指针。
  2. 遍历链表二,找出尾节点指针。
  3. 如果两个尾节点指针不为 nullptr 且相等,则两个链表相交。

查找相交的两个单向链表的第一个交点

这个问题是上面问题的扩展。通过观察两个相交链表的形状(Y字形),我们可以看到,如果从尾部看,从尾部到第一个交点的这部分节点是「对齐」的,而前面的长度不同。我们让前面也「右对齐」,这样比较是否相交节点的时候,只需要对比一次而不是遍历另一个节点。具体方法如下:

  1. 找出两个链表的长度 len1len2. 假设 len1 > len2.
  2. 让长的链表先遍历 len1 - len2 次。
  3. 两个链表一起遍历,每次都判断遍历到的是否是同一个节点。

如果单项链表是有环的,那又该如何找到交点呢?

  • 如果单项链表一个有环,一个没环,那么他们不可能相交;(因为有环之后,如果相交,则另一个一定也就有环了
  • 如果检测两个都有环(见下面的算法),那么可以先找到环的起点,然后以此处为结束点,查找两个链表到此位置的长度 len1 和 len2,然后再用上述方法来解决。

判断单项链表是否有环

问题描述

给定一个单项链表,判断链表中是否存在环。

算法一

遍历单项链表,并对已经遍历到的节点进行标记。每次遍历的时候,从标记过的集合里查找,如果找到相同节点,说明链表有环。时间复杂度为 O (n^2)。当然,也可以通过改进查找算法减少时间复杂度,但不会降低到 O (n)。

算法二

使用两个指针同时遍历链表。假设这两个指针分别叫快指针 ptrFast 和慢指针 ptrSlow

慢指针使用通常的方式遍历:每次遍历时有

ptrSlow = ptrSlow -> next;

快指针则以两倍的速度遍历:

ptrFast = ptrFast -> next;

设想:如果这个链表没有环,就如同一条直直的公路,快的一方永远不可能被慢的赶上。

但是,有环的时候,这种情况就不一样了:

因为快的指针进入环中并且不停循环,快指针和慢指针将很快相遇。

这种方法的时间复杂度为 O(n)。

查找链表元素

问题描述

查找链表中指定的元素:

  1. 找到链表中倒数第 k 个元素。
  2. 找到链表的中间元素。

算法一

我们先从直观上分析一下:要找到倒数第 k 个元素,必然要知道链表的长度,所以至少需要 O(n) 的时间。在不借助其他空间的情况下,此时我们无法反过来知道倒数第 k 个元素,因此必须重新遍历,所以至少需要遍历 2n - k 次。这种算法已经是很优秀的算法了,已经很难在不借助空间的情况下减少遍历了。

算法二

这个算法只是更「优雅」,其实没有变化:使用两个指针 ptrFirstptrSecond

对于第一个问题:让两个指针有 k 步的遍历步距差值,这样当第一个指针指向最后时,第二个指针正好指向倒数第 k 个。其实遍历的次数和算法一相同。网上有一些文章误认为这种方式更高效,其实没有太本质的变化,只有常数的变化。

具体来说,就是先让 ptrFirst 遍历了 k 个节点后,两个指针再开始一起遍历节点。

同样道理,对于第二个问题:让 ptrFisrt 以两倍的速度遍历(参见本文上面的「快指针」和「慢指针」部分),当第一个指针遍历到最后一个节点的时候,第二个指针正好遍历到中点。

思考题:

1、如何找到链表 1/3 位置的节点?

2、如何找到单链表中环的起点和长度?(Tip:可以通过将单链表增加一维标记位,通过遍历将标记位 域填充;如果发现有节点已经被填充该域,则说明有环;此时,这个点就是环的起点。时间复杂度 O(n),空间复杂度 O(n)。)

当前页阅读量为: