source: https://leetcode.com/problems/remove-duplicates-from-sorted-list/
C/C++ Solution to LeetCode problem 83. Remove Duplicates from Sorted List.
Problem
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.
Examples
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.
Solution
We will use two pointers, one to explore each node, and one to keep tracking of the list and the element that points next
.
- Initialize two pointers at the head.
- Move one pointer until the current node has a different value from the next node.
- Move once more this pointer.
- Point
next
of the other pointer to the pointer that moved first. - Move the pointer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *f = head;
ListNode *b = head;
while (f) {
if (f->next && f->val == f->next->val) {
f = f->next;
continue;
}
f = f->next;
b->next = f;
b = b->next;
}
return head;
}
};