Note:

一共会有三种情况

Case 1: 插在head；

Case 2: 插在中间

Case 3: 插在tail

Key word:

在0-based index处插ListNode

public class Solution {
  public ListNode insert(ListNode head, int index, int value) {
    ListNode cur = head;
    ListNode newNode = new ListNode(value);
    ListNode dummyHead= new ListNode(0);
    ListNode prev = dummyHead;
    prev.next = cur;
    int curIndex = 0;
    while (cur != null) {
      if (curIndex == index) {
        prev.next = newNode;
        newNode.next = cur;
      }
      prev = cur;
      cur = cur.next;
      curIndex++;
    }
    //如果插在tail
    if (curIndex == index) {
      prev.next = newNode;
    }
    return dummyHead.next;
  }
}

Complexity Analysis:

TC: O(N)

SC: O(1)