题解 | #链表中环的入口结点#
链表中环的入口结点
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
此题依旧是上道题的变种类型，难度不大，贴出代码和思路以供参考和之后的学习
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (hasCycle(pHead)==false) {
return null;
}
ListNode cur1=pHead;
ListNode cur2=pHead;
ListNode cur3=pHead;
while (cur1.next!=null&&cur1.next!=null) {
cur1=cur1.next;
cur2=cur2.next.next;
if (cur1==cur2) {
break;
}
}
while (cur1!=cur3) {
cur1 = cur1.next;
cur3 = cur3.next;
}
return cur1;
}
public boolean hasCycle(ListNode head){
if (head==null){
return false;}
ListNode cur1=head;
ListNode cur2=head;
while (cur2!=null&&cur2.next!=null){
cur1=cur1.next;
cur2=cur2.next.next;
if (cur1==cur2){
return true;
}
}
return false;
}
}
思路：先确定链表是否有环，运用之前的代码即可，其次，在默认有环的情况下，利用快慢指针法将两个指针在环中第一次碰见的节点记录，并在头结点新建立一个慢指针，和第一个慢指针同时走，当两个指针相遇的节点，就是目标节点
图是如下：
投递深圳同为数码等公司10个岗位