算法-单链表及环

算法-单链表及环

 

碰到一个问题,单链表及环的问题,整理一下各种解法:

 

1.1.    是否有环

  1. 链表唯一标识列表化,遍历链表,判断表中是否有当前节点唯一标识,有代表有环,无则将当前节点唯一标识加入列表。

时间复杂度最优,空间复杂度较高。

  1. 快慢指针,快指针移动步伐为2,慢指针移动步伐为1,如果两者相遇,则有环,如快指针为NULL,即到链尾,则无环。

 

1.2.    环的长度

  1. 链长度-无环长度,换句话说,(列表长度+1)-list.index(当前节点ID)
  2. 在慢指针进入环的时候,快指针到慢指针的距离为n,那么到二者相遇的时候,一定移动了n次;

现在快慢指针位置重合,再往前移动,移动r次两者再次相遇,说明快指针追上了慢指针,追的长度等于r等于环的长度。

 

1.3.    环的起点位置

  1. list.index(当前节点ID)
  2. 假设起点到环起点的长度为LenA;开始到第一次相遇,移动了t步;环的长度为R;环的起点到二者第一次相遇位置的距离为x,二者相遇的时候快指针已经在环上转了n圈。

则有如下等式成立: 慢指针移动的距离=LenA + x; 即 t = LenA + x;

快指针移动的距离=LenA + n * R + x; 即 2t = LenA + n * R + x;

所以 2*(LenA+x) = LenA + n*R + x;

即 LenA = n * R – x;

上面的等式可以这样理解,如果慢指针从链表起点开始移动,快指针从环起点开始移动,当慢指针从起点走到环起点的时候,快指针一直在环上移动,而且还差x步就移动了n圈。进而可以得到结论,如果慢指针从链表起点开始移动,快指针从二者第一次相遇点开始移动,当慢指针到达环起点的时候,快指针也正好达到环起点,即二者指向相同的节点。

转载于:https://www.cnblogs.com/wodeboke-y/p/9971609.html

    原文作者:akuibpt23191
    原文地址: https://blog.csdn.net/akuibpt23191/article/details/101129497
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞