快指针一次走两步、慢指针一次走一步,在第一次相遇节点停下, 快指针 回到头 慢指针留在原地 同时每次分别走一步,在第一个入环节点处相遇
public Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null)
return null;
Node slow = head.next;
Node fast = head.next.next;
while (slow != fast) {
if (fast.next == null || fast.next.next == null)
return null;
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇后 fast 回到头 slow留在原地 同时各走一步
fast = head;
while (fast != slow) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
C++ | Java |
---|