Linked List Insert

If we want to add a new value after a given node prev, we should:

1. Initialize a new node cur with the given value;

   
2. Link the "next" field of cur to prev's next node next;

   
3. Link the "next" field in prev to cur.

   

Three steps:

1. Create the target node

2. Direct target node's reference to pre node's next. So currently, there are two pointers aiming at the same next node.

3. Redirect pre's next to target node.

Otherwise, if we set pre's next to the target first and then set target's next to pre's next, target's reference is directing to itself. The circular loop will be a mess. One way to avoid that is to store the pre's next before redirecting pre's reference, and set target's reference to the specifc stored next. And in this way it will take O(3) space instead of O(2) in the previous method.