This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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\n

'
\n

**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.

**Java**

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

**Complexity Analysis**

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.

\nSpace complexity is since no additional space is used.

\n**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:

\n\nAll nodes in the list up to the pointer

\n`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.

- \n
- \n

\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 - \n

\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

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.

Analysis written by: @noran.

\n