[数据结构]快慢指针与滑动窗口

快慢指针找中点的原理很简单· 两个指针同时从头出发slow 每次走 1 步fast 每次走 2 步。· 当 fast 走到末尾fast NULL 或 fast-next NULL时slow 刚好走到链表中间。为什么刚好设链表长度为 n。· fast 走的路程是 slow 的两倍。· 当 fast 走完 n 步或 n-1 步取决于奇偶时slow 恰好走了 n/2 步向下取整。· 对于偶数长度fast 到达末尾 NULLslow 在 n/2 位置即后半部分的第一个节点。· 对于奇数长度fast 停在最后一个节点fast-next NULLslow 在正中间节点。直观比喻想象两个人从同一位置出发一个人跑的速度是另一个人的两倍。当跑得快的人到达终点时跑得慢的人正好在全程一半的位置。所以快慢指针是找链表中心最常用、最高效的方法O(n) 时间O(1) 空间。