Introduction
LeetCode 83: Remove Duplicates from Sorted List is a fundamental linked list problem. Given a sorted singly linked list, the task is to remove all duplicates in-place such that each element appears only once.
This is a great beginner-level problem to practice pointer manipulation and linked list traversal in Go.
Problem Statement
Given the head of a sorted linked list, delete all duplicates such that each element appears only once.
Return the head of the modified list.
Example:
go
Input: 1 -> 1 -> 2
Output: 1 -> 2
Input: 1 -> 1 -> 2 -> 3 -> 3
Output: 1 -> 2 -> 3
Approach: Single Pointer Traversal
Strategy:
Since the list is sorted, duplicate elements will be adjacent. We can solve this problem by:
- Starting with the head node.
- Comparing the current node with its next node.
- If the values are the same, we skip the next node.
- Otherwise, we move to the next node.
Repeat until we reach the end of the list.
Go Implementation
go
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
current := head
for current != nil && current.Next != nil {
if current.Val == current.Next.Val {
// Skip the duplicate node
current.Next = current.Next.Next
} else {
current = current.Next
}
}
return head
}
Explanation
- We loop through the list as long as
current and current.Next are not nil.
- If
current.Val == current.Next.Val, we bypass the duplicate node.
- Else, we simply advance the pointer.
This ensures only the first occurrence of each number remains.
Time and Space Complexity
MetricComplexityTime ComplexityO(n)Space ComplexityO(1)
Where n is the number of nodes in the linked list. We only use one pointer and modify the list in-place.
Edge Cases
- Empty list → returns
nil.
- List with no duplicates → remains unchanged.
- All nodes are the same → only one node remains.
Conclusion
LeetCode 83 is a classic problem to reinforce your understanding of in-place modification of linked lists. The fact that the list is sorted simplifies the logic significantly.