考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默响起来一个声音:”乔戈里峰”
每天一道剑指offer-链表中环的入口结点 https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
思路
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean flag = true;
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null || pHead.next == null)
return null;
ListNode pNode = judgeHasChain(pHead);//判断是否有环
if(pNode != null)
{
int lengthChain = 1;
ListNode pNodeCopy = pNode.next;
while(pNodeCopy != pNode)
{//这个节点已经在环里面了!
lengthChain++;
pNodeCopy = pNodeCopy.next;//计算环的长度
}
ListNode fast = pHead;
ListNode slow = pHead;
int temp = 0;
while(temp < lengthChain)
{//快指针先走环的长度
fast = fast.next;
temp++;
}
while(fast != slow)
{//快慢指针一起走,因为快指针先走了环长度,当慢指针刚一进环,由于快指针刚好多走了环长度,所以快指针整好走了一个环的周期呀,所以快指针必然也在环的入口
fast = fast.next;
slow = slow.next;
}
return fast;
}
return null;
}
private ListNode judgeHasChain(ListNode pHead)
{
ListNode fast = pHead.next;
ListNode slow = pHead;
while(fast != slow)
{
if(fast != null && fast.next != null)
{//快指针走一步
fast = fast.next;
}else{
flag = false;
break;
}
if(slow != null && slow.next != null)
{//慢指针走一步
slow = slow.next;
}else{
flag = false;
break;
}
if(fast == slow)
{//两者相等,说明相遇了,有环
return fast;
}else{
fast = fast.next;//快指针多走一步
}
}
if(flag)
return fast;
return null;
}
}