Remove Duplicates from Sorted List
Description
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example 1:
Input: head = [1,1,2]
Output: [1,2]
Explanation: The list 1->1->2 has duplicate value 1. After removing the duplicate, the list becomes 1->2.
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: The list 1->1->2->3->3 has duplicates at values 1 and 3. After removing duplicates, the list becomes 1->2->3.
Example 3:
Input: head = []
Output: []
Explanation: The empty list remains empty after removing duplicates.
Constraints
The number of nodes in the list is in the range [0, 300]-100 <= Node.val <= 100The list is guaranteed to be sorted in ascending order
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Two pointers / in-place modification
- Approach
- Use a pointer to traverse. For each node, skip all following nodes with the same value by adjusting next pointers.
- Complexity
- Single pass through the list in O(n)
Solutions
Show PY Solution
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def solution(head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
slow = head
fast = head.next
while fast:
# print(slow.val, fast.val)
if slow.val == fast.val:
# print("Removing ", fast.val)
slow.next = fast.next
else:
slow = fast
# slow = fast
fast = fast.next
# n = head
# while n:
# print(n.val, end=" ")
# n = n.next
return head