给你单链表的头结点head = [1,2,3,4,5,6] ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。用java写
时间: 2024-09-18 18:02:56 浏览: 42
数据结构课程设计单链表操作.doc
在Java中,我们可以使用快慢指针法来找到单链表的中间节点。快指针每次移动两步,慢指针每次移动一步。当快指针到达链表尾部时,慢指针正好位于中间位置,或者离中间两个节点处。
以下是实现这个算法的Java代码:
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode findMiddleNode(ListNode head) {
if (head == null || head.next == null) {
return head; // 单个元素或空链表的情况
}
ListNode slow = head; // 慢指针
ListNode fast = head.next; // 快指针
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next; // 快指针每次前进两步
}
return slow; // 返回慢指针,即为中间节点
}
```
在这个代码中,我们首先检查链表是否为空或只有一个节点。然后,初始化慢指针和快指针,并在一个循环里让它们分别向前移动。当快指针到达链表的末尾(即`fast.next`为null)时,慢指针就是我们要找的中间节点或距离中间节点一个的位置。
阅读全文