题解 | #链表中环的入口结点#
方法1：Set
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
//思路：用set，当首次出现相同节点（插入失败时），该节点就是入口
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null) return null;
Set<ListNode>set=new HashSet<>();
boolean success=true;
while(pHead!=null){
success=set.add(pHead);
if(!success) return pHead;
pHead=pHead.next;
}
return null;
}
}
方法2、快慢节点法，快节点每次走2步，慢节点每次走1步，当快慢节点第一次相遇时，快节点刚好领先k个环的长度。
此时快节点重新出发，将快节点的速度设置为1。当二者再次相遇时就是环的开头。
假设非环节点数为a，环中节点数为b，慢节点走了s步，那快节点就走了2s步，有以下公式：
- 2s=s+kb
此时如果把快指针放在开头以1的速度前进，那么快慢指针在同时前进a时就会相遇在程序入口。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
//思路：快慢节点法，快节点每次走2步，慢节点每次走1步，当快慢节点第一次相遇时，快节点刚好领先k个环的长度。
//此时快节点重新出发，将快节点的速度设置为1。当二者再次相遇时就是环的开头。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null) return null;
ListNode fast=pHead,slow=pHead;
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow) break;
}
if(fast.next==null||fast.next.next==null)
return null;
fast=pHead;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return fast;
}
}
投递中移(苏州)软件技术有限公司等公司10个岗位 >
