算法小知识------10.16----关于链表的相关算法(2)
如果链表有环，求出环的长度
求出环的长度，可以在之前判断是否有环的基础上，做出修改
首先，在确定有环的前提下，求出环的长度
在首次两指针相等的节点开始，再次出发，直到再次回到该节点的时候，就证明已经完成一圈了
也可以用双指针的方法去实现，双指针在相等节点同时出发，A节点速度比B节点快，当两节点再次相遇时，A节点追上B节点并且超出了相应的距离。A和B的速度差决定了A比B多走了几圈
实现
基于空间复杂度的考虑，采用第一种方法，并且结合之前的判断有环方法
/**
* 判断是否有环并且输出环的长度
*
* @param head 链表头节点
*/
public static Integer isCycle(ListNode head){
ListNode p1 = head;
ListNode p2 = head;
while(p2 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){
return getCycleLength(p1);
}
}
return 0;
}
/**
* 求出链表的环长度
*
* @param head 链表
*/
public static Integer getCycleLength(ListNode head){
if(head == null){
return 0;
}
ListNode p1 = head;
Integer length = 0;
while(p1 != null){
p1 = p1.next;
length++;
if(p1 == head){
return length;
}
}
return 0;
}复制代码如果链表有环，求出 入环的节点
在上述实现了判断链表是否有环，求出环的长度，延伸拓展入环的节点
首先，头结点到入环节点的距离为D
入环节点到首次相遇为S1，首次相遇到入环节点为S2
节点A到第一次相遇的距离为：D+S1；节点B到第一次相遇的距离为：D+S1+n(S1+S2);n为速度差
因为节点B的速度是节点A的2倍，所以：2(D+S1) = D+S1+n(S1+S2) ;
整理得： D = (n-1)(S1+S2)+S2；也就是说从链表头结点到入环点的距离，等于从首次相遇点绕环
n-1圈再回到入环点的距离。
所以只需要一个指针放在头节点，一个指针放在首次相遇节点，再次相遇时，则为入环节点
实现
/**
* 输出环的入环节点
*
* @param head 链表头节点
*/
public static Integer isCycle(ListNode head){
ListNode p1 = head;
ListNode p2 = head;
while(p2 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
while(p1 == p2){
p1 = head;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1.val;
}
}
return 0;
}
作者：Jayhaw_花
链接：https://juejin.cn/post/7019599811900882952