java算法:找到单链表的中间节点
2022-01-21 本文已影响0人
Bfmall
实现思路:
通过快慢指针,快指针每次跳两个节点,慢指针每次跳一个节点,当快指针移动到末尾时,慢指针整好指向链表的中间节点。
/**
* 算法:找到单链表的中间节点
* 通过快慢指针,快指针每次跳两个节点,慢指针每次跳一个节点,当快指针移动到末尾时,慢指针整好指向链表的中间节点。
* [A] -> [B] -> [C] -> [D] -> [E] -> [F]
*
* 初始指针 f0
* s0
* 第一次 s1 f1
* 第二次 s2 f2
* 第三次 s3 f3 (已经遍历完毕链表,越界)
* @param node
* @return
*/
public Node getMiddleNode(Node node) {
if (node == null) {
return null;
}
Node fastNode = node;
Node slowNode = node;
while (fastNode != null && fastNode.next != null && slowNode != null) {
fastNode = fastNode.next.next;//跳两步
slowNode = slowNode.next;//跳一步
}
return slowNode;
}