Problem 10

key point：找到mid node

option 1:

• 数一下一共有多少的node

• 再从头出发走n/2个node

option 2:

• 快慢指针，过例子看

  • 初始条件：slow = fast = head

  • 截止条件：fast == null/ fast.next == null

ListNode deleteMiddle(ListNode head) {
    if (head == null) {
    return null;
    }
    ListNode dummy = new ListNode();
    dummy.next = head;

    ListNode prev = dummy;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null || fast.next != null) {
        slow = slow.next;
        prev = prev.next;
        fast = fast.next.next;
    }
    prev.next = slow.next;
    return dummy.next;
}