算法

本文主要是介绍算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

判断链表是否存在环：

https://www.jianshu.com/p/95cd7eb17856

给定一个单链表，已知头结点
1. 如何判断链表是否存在环?
2. 如何知道环的长度?
3. 如何找出环的连接点在哪里?
4. 带环链表的长度?

解法：

1. 对于问题1
使用追赶的方法,设定两个指针show,fast,从头节点开始,每次分别前进1步,2步,如存在环则两者必然会相遇,如不存在环,则fast遇到null退出,并且碰撞点到头节点的距离为环中节点数n.
2. 对于问题2:
记录下问题1的碰撞点p,碰撞点p肯定是在环中的,从这个节点触发,一边移动一边计数再次回到这个节点就得到了环中节点数n
3. 对于问题3:
有定理: 碰撞点p到连接点的距离=头节点到连接点的距离,因此分别从碰撞点,头节点相同速度开始走相遇的那个点就是连接点.
定理证明如下:
设头节点到连接点的距离为x,连接点到碰撞点的距离为y,碰撞点到连接点的距离为z,环的长度为n,
	(1) 碰撞点到头节点的距离为n,则有x+y=n
	(2) 又因为环的长度为n,则有y+z=n
	(3) 由(1),(2) 可得,碰撞点p到连接点的距离=头节点到连接点的距离
4. 对于问题4
问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环链表的长度.

两个无环链表是否存在交点：

给定两个无环的链表，判断两者是否有交点

解法：

直接将较小的链表，首尾相连，然后按照第一个问题的去找环，以及环的起点

这篇关于算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！