使用两个节点,slow和fast,分别行进1步和2步。如果有相交的情况,slow和fast必然相遇;如果没有相交的情况,那么slow或fast必然有一个为null
相遇时有两种可能:1. 只是节点相交的情况,即:slow == fast但是 slow.next != fast.next
2. 链表中存在环,即slow == fast 而且 slow.next == next
实现代码:
public bool HasCycle(ListNode head) {
// - for null node , false
if(head == null || head.next == null){
return false;
}
if(head.val != head.next.val && head.next.next == null){
return false;
}
var slow = head;
var fast = head;
while(true) {
slow = slow.next;
if(fast.next != null){
fast = fast.next.next;
}
else{
return false;
}
if(slow == null || slow.next == null || fast == null || fast.next == null) {
return false;
}
if(slow.val == fast.val && slow.next.val == fast.next.val){
return true;
}
}
return false;