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]
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
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.
Solutions
Solution 1: Single Pass
We use a pointer $cur$ to traverse the linked list. If the element corresponding to the current $cur$ is the same as the element corresponding to $cur.next$, we set the $next$ pointer of $cur$ to point to the next node of $cur.next$. Otherwise, it means that the element corresponding to $cur$ in the linked list is not duplicated, so we can move the $cur$ pointer to the next node.
After the traversal ends, return the head node of the linked list.
The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 91011121314
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defdeleteDuplicates(self,head:Optional[ListNode])->Optional[ListNode]:cur=headwhilecurandcur.next:ifcur.val==cur.next.val:cur.next=cur.next.nextelse:cur=cur.nextreturnhead
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcdeleteDuplicates(head*ListNode)*ListNode{cur:=headforcur!=nil&&cur.Next!=nil{ifcur.Val==cur.Next.Val{cur.Next=cur.Next.Next}else{cur=cur.Next}}returnhead}