Java 中链表的中间节点

在本节中，我们将学习如何在 Java 中查找链表的中间节点。我们还将探讨查找中间节点的各种方法。

给定：给定链表的第一个节点或头节点（在本例中为 14）

14 -> 16 -> 17 -> 11 -> 15 -> 18 -> 13 -> 12 -> NULL

返回

15

给定

13 -> 17 -> 90 -> 76 -> 45 -> 32 -> 10 -> NULL

返回

76

方法 1：使用两个指针

在此方法中，我们将使用两个指针，一个快指针（一次移动两步），另一个慢指针（一次移动一步）。显然，快指针比慢指针先到达列表的末尾。当快指针到达链表的末尾时，我们检查一次移动一步的慢指针的位置。慢指针指向的节点就是链表的中间节点。

文件名： TwoPointerExample1.java

输出

The middle node of the linked list is: 15

方法 2：使用栈

在此方法中，我们将使用栈来查找链表的中间节点。首先，我们将找到链表的总大小。然后，我们将链表中的所有节点压入栈中。然后，我们将总大小除以 2，然后 whatever number comes，我们执行 pop 操作直到达到该数字的次数。栈顶或 peek 节点就是我们的答案；即中间节点。

文件名： StackExample1.java

输出

The middle node of the linked list is: 76

方法 3：使用队列

在此方法中，我们将使用队列来查找链表的中间节点。首先，我们将找到链表的总大小。然后，我们将链表中的所有节点压入队列中。然后，我们将总大小除以 2，然后 whatever number comes，我们执行出队操作直到达到该数字的次数。队列的顶部或 peek 节点就是我们的答案；即中间节点。

文件名： QueueExample1.java

输出

The middle node of the linked list is: 76

方法 4：使用一个指针

在此方法中，我们将只使用一个指针来查找链表的中间节点。首先，我们将找到链表的总大小。然后，我们将总大小除以 2，然后 whatever number comes，我们从头节点开始移动指针，移动该次数。指针指向的节点就是链表的中间节点。

文件名： OnePointerExample1.java

输出

The middle node of the linked list is: 76

方法 5：使用计数器

在此方法中，我们还将使用两个指针，借助计数器来查找链表的中间节点。每次移动到下一个节点时，我们将计数器加 1。当计数器的值是奇数时，我们将另一个指针（例如奇数指针）从头节点开始移动。迭代结束后，奇数指针指向的位置就是中间节点。

文件名： CounterExample.java

输出

The middle node of the linked list is: 76