logologo

找到链表的第一个入环节点,如果无环,返回 NULL

Sep 5, 2023

快指针一次走两步、慢指针一次走一步,在第一次相遇节点停下, 快指针 回到头 慢指针留在原地 同时每次分别走一步,在第一个入环节点处相遇

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
浙ICP备2021022773号    2022-PRESENT © ZhengKe