## 83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given `1->1->2`, return `1->2`.
Given `1->1->2->3->3`, return `1->2->3`.

b'
\n

## Solution

\n
\n

#### Straight-Forward Approach [Accepted]

\n

Algorithm

\n

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.

\n

Java

\n
`public ListNode deleteDuplicates(ListNode head) {\n    ListNode current = head;\n    while (current != null && current.next != null) {\n        if (current.next.val == current.val) {\n            current.next = current.next.next;\n        } else {\n            current = current.next;\n        }\n    }\n    return head;\n}\n`
\n

Complexity Analysis

\n

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.

\n

Space complexity is since no additional space is used.

\n

Correctness

\n

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:

\n
\n

All nodes in the list up to the pointer `current` do not contain duplicate elements.

\n
\n

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.

\n
\n
1. \n

`current.next` was a duplicate of `current`. In this case, the duplicate node at `current.next` is deleted, and `current` stays pointing to the same node as before. Therefore, the condition still holds; there are still no duplicates up to `current`.

\n
2. \n
3. \n

`current.next` was not a duplicate of `current` (and, because the list is sorted, `current.next` is also not a duplicate of any other element appearing before `current`). In this case, `current` moves forward one step to point to `current.next`. Therefore, the condition still holds; there are no duplicates up to `current`.

\n
4. \n
\n

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.

\n

Analysis written by: @noran.

\n
'