Java单链表查找中间值快慢指针和计数法
时间: 2024-09-25 14:19:05 浏览: 5
在Java中,寻找单链表的中间节点通常有两种常用方法:快慢指针法(也称为龟兔赛跑算法)和双指针法,其中一种就是计数法。
**快慢指针法:**
这种方法利用两个指针,一个快速指针每次移动两步,另一个慢速指针每次移动一步。当链表长度为奇数时,相遇的那个点就是中间节点;如果链表长度为偶数,那么当快速指针到达尾部时,慢速指针刚好位于链表的中间位置。
**计数法:**
这种方法需要预处理链表长度,通过遍历链表同时计算元素个数。可以维护两个指针,一个普通遍历,一个记录已访问元素的数量,当已访问元素数量等于链表总长度的一半时,此时的指针指向的就是中间节点。
下面是简单的代码示例:
```java
// 使用快慢指针法
public ListNode findMiddleNode(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // 返回慢指针,即中间节点
}
// 使用计数法(假设有一个已经计算好链表长度的函数ListNode length(ListNode head))
public ListNode findMiddleNode(ListNode head, int length) {
ListNode current = head, count = 0;
while (current != null) {
count++;
current = current.next;
}
current = head;
for (int i = 0; i < length / 2; i++) {
current = current.next;
}
return current; // 返回当前节点,即中间节点
}
```