Solution
Approach 1: StraightForward Approach
Algorithm
This is a simple problem that merely tests your ability to manipulate list node pointers. Because the input list is sorted, we can determine if a node is a duplicate by comparing its value to the node after it in the list. If it is a duplicate, we change the next
pointer of the current node so that it skips the next node and points directly to the one after the next node.
Complexity Analysis

Time complexity : . Because each node in the list is checked exactly once to determine if it is a duplicate or not, the total run time is , where is the number of nodes in the list.

Space complexity : . No additional space is used.
Correctness
We can prove the correctness of this code by defining a loop invariant. A loop invariant is condition that is true before and after every iteration of the loop. In this case, a loop invariant that helps us prove correctness is this:
All nodes in the list up to the pointer
current
do not contain duplicate elements.
We can prove that this condition is indeed a loop invariant by induction. Before going into the loop, current
points to the head of the list. Therefore, the part of the list up to current
contains only the head. And so it can not contain any duplicate elements. Now suppose current
is now pointing to some node in the list (but not the last element), and the part of the list up to current
contains no duplicate elements. After another loop iteration, one of two things happen.

current.next
was a duplicate ofcurrent
. In this case, the duplicate node atcurrent.next
is deleted, andcurrent
stays pointing to the same node as before. Therefore, the condition still holds; there are still no duplicates up tocurrent
. 
current.next
was not a duplicate ofcurrent
(and, because the list is sorted,current.next
is also not a duplicate of any other element appearing beforecurrent
). In this case,current
moves forward one step to point tocurrent.next
. Therefore, the condition still holds; there are no duplicates up tocurrent
.
At the last iteration of the loop, current
must point to the last element, because afterwards, current.next = null
. Therefore, after the loop ends, all elements up to the last element do not contain duplicates.