Approach 1: Straight-Forward Approach
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.
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.
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
currentdo 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.nextwas a duplicate of
current. In this case, the duplicate node at
current.nextis deleted, and
currentstays pointing to the same node as before. Therefore, the condition still holds; there are still no duplicates up to
current.nextwas not a duplicate of
current(and, because the list is sorted,
current.nextis also not a duplicate of any other element appearing before
current). In this case,
currentmoves forward one step to point to
current.next. Therefore, the condition still holds; there are no duplicates up to
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.