找到链表的中间结点
[!Tip]
本节源代码见Github链接🔗
问题描述
找到链表的中间结点
核心思路
通过移动速度不同的双指针解决，核心包含以下3步：
- 定义一个指向链表头节点的指针slowPtr，和一个指向头结点的后继结点的指针fastPtr；
- 两个指针同时向前移动，slowPtr每次移动一个结点，fastPtr每次移动两个结点；
- 当fastPtr移动到表尾时，停止移动，此时slowPtr停在链表中间结点。（第 (n/2) 个结点为中间结点，需要注意链表结点数奇偶性问题）
实现代码
【👉🏻>>点击展开查看代码】
/**
* 找到单向链表的中间结点
*
* @param headNode
* @return NormalListNode
* @author: Max Solider
* @date: 2022/10/9 14:18
*/
NormalListNode findMiddle(NormalListNode headNode) {
if (headNode == null || headNode.getNext() == null) {
return headNode;
}
NormalListNode slowPtr = headNode;
NormalListNode fastPtr = headNode.getNext();
while (fastPtr.getNext() != null && fastPtr.getNext().getNext() != null) {
fastPtr = fastPtr.getNext().getNext();
slowPtr = slowPtr.getNext();
}
NormalListNode middleNode = null;
if (fastPtr.getNext() == null) {
middleNode = slowPtr;
} else {
middleNode = slowPtr.getNext();
}
System.out.println("The middle node of linked lis is " + middleNode.getData());
return middleNode;
}
时间复杂度
时间复杂度为O(n)，用于遍历链表。
空间复杂度
空间复杂度为O(1)，用于存储临时变量。