java - 如何从链表的中间元素中找到第二个元素？

Question

面试中问我求链表中间节点起第二个节点的值？他们希望在 O(n) 时间复杂度内完成此操作。

我试图给出使用 O(n2) 获取中间元素的答案。但这无济于事。然后尝试使用慢指针和快指针在 O(n) 中完成。

节点慢，快；

    while (slow.next != null and fast.next.next != null){

    }

例如。输入链表:1 2 3 4 5 6 7 8 9 输出节点:7

因为中间节点是 5 并且它的第二个元素是 7。

非常感谢解决方案。

Answer 1

Node getSecondAfterMind(Node head) {
  Node slow = head, fast = head;
  while(fast.next.next != NULL) {
    slow = slow.next;
    fast = fast.next.next;
  }
  if slow.next!= NULL && slow.next.next != NULL {
      return slow.next.next;
  }

   return NULL;
}