链表的中间结点
难度:
标签:
题目描述
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
提示：
- 链表的结点数范围是
[1, 100] 1 <= Node.val <= 100
代码结果
运行时间: 32 ms, 内存: 14.9 MB
/*
题目思路：
1. 使用 Java Stream 将链表转换为列表。
2. 获取列表的大小，并找到中间位置。
3. 返回从中间位置开始的子列表。
*/
import java.util.*;
import java.util.stream.*;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode middleNode(ListNode head) {
List<ListNode> list = new ArrayList<>();
for (ListNode node = head; node != null; node = node.next) {
list.add(node);
}
return list.get(list.size() / 2);
}
}解释
方法:
这个题解使用了快慢指针的思路。初始时，快指针 fast 和慢指针 slow 都指向链表的头节点。快指针 fast 每次走两步，慢指针 slow 每次走一步。当快指针到达链表尾部时，慢指针正好到达链表的中间节点。通过这种方式，只需要遍历一次链表就可以找到中间节点。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在链表有偶数个节点的情况下，快慢指针算法如何保证返回的是第二个中间节点而不是第一个？
▷🦆
如果链表只有一个节点时，快慢指针的行为是怎样的？请解释其逻辑。
▷🦆
为什么在快指针移动前需要检查`fast`和`fast.next`是否为`None`？
▷🦆
这种快慢指针的方法在面对大规模数据时，其性能表现如何？即使是O(n)，是否有进一步优化的可能性？
▷