一般用Fast and Slow pointers 来找中点。
这个时候,有两种写法。
第一种
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
第二种
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
对于list包含奇数个node的情况,上面两种slow pointer最终都指向中间那个数,比如1 -> 2 -> 3 -> null,slow -> 2
对于list包含偶数个node的情况,比如1 -> 2 -> 3 -> 4 -> null,第一种情况slow -> 3,第二种slow -> 2