1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

都知道fast从head出发, slow最后的位置要么是正中间, 要么是右半部分开头. 如果fast从head.next出发, slow要么在正中间, 要么是左半部分最后一个. 现在我们想让slow在正中间左边一个或者左半部分最后一个停, fast应该在什么位置? 此时fast应该在head.next.next. 自己画了个图搞明白了.

时间复杂度: O(n)
空间复杂度: O(1)