判断链表是否为带环链表
方法一、快慢指针移动判断
首先如何判断链表是否有环，这个时候首先需要知道链表是否为空，如果不为空，则继续判断。
思路：首先定义两个变量，一个fast,一个slow，让fast 每次走两步，slow每次走一步，当fast和slow相遇时，即是该链表存在环结构。如果该链表为无环结构，则当遍历完这个链表时也不会相遇。即是返回false。
图例如下：
图中为了说明情况，
fast指针初始标记为f0,每移动一次加1，如f1,f2,f3....
slow指针初始标记为s0,每移动一次加1，如s1,s2,s3....
5660a8da20b37b4a5a820604efb8205.png
代码实现如下：
//初始化一个有环的链表Node
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeF;
nodeF.next = nodeD;//此时F节点又指向了D节点，已经产生了环状
/**
* 判断链表是否有环 （快慢指针的方式）
* <-----------------
* | |
* [A] -> [B] -> [C] -> [D] -> [E] -> [F]
*
* 初始指针 f0
* s0
* 第一次 s1 f1
* 第二次 s2 f2
* 第三次 s3/f3
* 本例中即第三次遍历就判断出链表有环
* @param node
* @return
*/
private boolean hasCycle(Node node) {
if (node == null) {
return false;
}
Node fast = node;
Node slow = node;
//此字段仅用来记录遍历次数
int traverseCount = 0;
while (fast != null && fast.next != null && slow != null) {
fast = fast.next.next;//移动2步
slow = slow.next;//移动1步
traverseCount ++;
if (fast == slow) {
//如果碰面，就代表有环
Log.d(TAG, "hasCycle==>有环...traverseCount="+traverseCount);
return true;
}
Log.d(TAG, "hasCycle==>已经遍历次数...traverseCount="+traverseCount);
}
Log.d(TAG, "hasCycle==>无环");
return false;
}
方法二：使用Set<>集合记录Node元素，如果有重复元素则认为有环
代码实现如下：
/**
* 通过Set集合记录值的方式，如果有重复的数据，就代表有环
* @param node
* @return
*/
private boolean hasCycle2(Node node) {
Set<Node> nodeSet = new HashSet<>();
//此字段仅用来记录遍历次数
int traverseCount = 0;
while (node != null) {
if (nodeSet.contains(node)) {
Log.d(TAG, "hasCycle2==>有环...traverseCount="+traverseCount);
return true;
}
traverseCount ++;
Log.d(TAG, "hasCycle2==>traverseCount="+traverseCount);
nodeSet.add(node);
node = node.next;
}
Log.d(TAG, "hasCycle2==>无环");
return false;
}
三、扩展：（内容参考：https://blog.csdn.net/weixin_40879743/article/details/90646399）
如果链表有环，找到有环的入口点是哪个节点（如上图，入口点就是节点D，下面要找到这个节点）
思路：s=vt（路程=速度*时间）用方程思想列等式解
因为路程知道，速度知道（二倍关系），时间也知道（相等），所以可以列等式求关系。再用代码体现出关系，就可以解决这道题了。
如图：假设链表是Link fast是快的那个指针，Slow是慢的呢个指针，蓝色是fast走过的路程，绿色是slow走过的路程
K是环的入口，P是快慢指针相遇的地方
a，b，c 分别代表三段长度。
image.png
所以图就可以变成：
image.png
然后，让指针从 相遇点p 和 起始点first 同时遍历，这样由于 c = a , 所以p和first在k相遇，而k就是入口点。
代码实现如下：
/**
* 如果有环，获取相遇点的node
* @param node
* @return
*/
private Node getMeetNode(Node node) {
if (node == null) {
return null;
}
Node fast = node;
Node slow = node;
//此字段仅用来记录遍历次数
int traverseCount = 0;
while (fast != null && fast.next != null && slow != null) {
fast = fast.next.next;//移动2步
slow = slow.next;//移动1步
traverseCount ++;
if (fast == slow) {
//如果碰面，就代表有环
Log.d(TAG, "hasCycle==>有环...traverseCount="+traverseCount);
return fast;
}
Log.d(TAG, "hasCycle==>已经遍历次数...traverseCount="+traverseCount);
}
return null;
}
/**
* 如果有环，获取环出现的入口点
* @return
*/
public Node getCycleEntry(Node node) {
Node meetNode = getMeetNode(node);
Node p = meetNode;//相遇点元素的指针
Node first = node;//链表第一个元素的指针
while(p != first) {
//两个指针都进行移动，当相等的时候就找到了入口点
first = first.next;
p = p.next;
}
return p;
}
/**
* 将入口点打印出来：
*/
Node entryNode = getCycleEntry(nodeA);
Log.d(TAG, "有环的链表入口点Node Value="+entryNode.value);
网友评论