Remove Duplicates from Sorted List
Description
- Given the
headof a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Constraints
- The number of nodes in the list is in the range
[0, 300]. -100 <= Node.val <= 100- The list is guaranteed to be sorted in ascending order.
Test Cases
-
Input:
head = [1,1,2]Output:[1,2] -
Input:
head = [1,1,2,3,3]Output:[1,2,3]
Code
Approach 1: Iterative
Explanation
- Traverse the list from the head (or start) node.
- While traversing, compare each node with its next node.
- If the data of the next node is the same as the current node then delete the next node.
- Before we delete a node, we need to store the next pointer of the node.
- Repeat step 2 until the next node of the current node is the NULL pointer.
Analysis
- Time Complexity:
O(n) - Space Complexity:
O(1)