快慢指针:slow指针一次走一个节点,fast指针一次走两个节点,当fast指针到达链表末尾时,slow指针正好位于中间。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
复杂度分析
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。