Note: 三种cases

Case 1: 删头

Case 2: 删中间

遇到头会变的情况，使用dummyHead

因为要删除结点，所以需要记录被删结点后的ListNode，需要next

需要被删结点前的ListNode，需要prev

需要记录index

Key word:

在index处删ListNode

public class Solution {
  public ListNode deleteNode(ListNode head, int index) {
    //corner case
    if (head == null) {
      return null;
    }
    ListNode dummyHead = new ListNode(0);
    ListNode prev = dummyHead;
    ListNode cur = head;
    prev.next = cur;
    int curIndex = 0;
    while (cur != null) {
      ListNode next = cur.next;
      if (curIndex == index) {
        prev.next = next;
      }
      prev = prev.next;
      cur = next;
      curIndex++;
    }
    return dummyHead.next;
  }
}

Complexity Analysis:

TC: O(N)

SC: O(1)