83. Remove Duplicates from Sorted List

83. Remove Duplicates from Sorted List

Summary

Given the head of a sorted linked list, delete all duplicates so that each element appears only once. Return the sorted linked list.

Approach

Because the list is sorted, duplicate values always appear next to each other.

One approach is to use two pointers:

• current: the last unique node
• head: the node currently being scanned

If head.val is the same as current.val, move head forward. If the value is different, connect current.next to head and move current.

A cleaner approach is to use one pointer and remove duplicates in place.

Function 1

Set current = head and ans = head.

While head: If head.val == current.val: head = head.next Else: current.next = head current = head

If current: current.next = head

Return ans.

Function 2

Set current = head.

While current and current.next: If current.val == current.next.val: current.next = current.next.next Else: current = current.next

Return head.

Complexity

Time Complexity: O(N) Space Complexity: O(1)