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。

非常感谢解决方案。

标签： javaalgorithmdata-structures

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;
}