题目描述
思路
这些链表的有序性使这些操作都不难写。
前面在数组的题目里写过跳过重复元素的算法,这个和那个类似,用快慢指针写,但是由于这个是删除重复元素,所以我用了两个相邻的慢指针,左边的慢指针其实是为了保存真正的慢指针的上一个位置。
代码如下:
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == nullptr || head -> next == nullptr){
return head;
}
ListNode* slow1 = new ListNode(-1,head);
ListNode* slow2 = head;
ListNode* fast = head;
while(slow2!= nullptr){
if(slow2 -> next != nullptr
&& slow2 -> val == slow2 -> next -> val){
//发现了重复元素,开始使用fast指针跳过这些重复元素
fast = slow2;
while(fast != nullptr &&
fast -> val == slow2 -> val){
fast = fast-> next;
}
if(slow2 == head){
head = fast;
}
//如果在开头删除了元素的话,需要更新head指针
slow1 -> next = fast;
slow2 = slow1 -> next;
continue;
}
slow1 = slow1 -> next;
slow2 = slow2 -> next;
}
return head;
}
};
官方题解如下:
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) {
return head;
}
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur->next && cur->next->next) {
if (cur->next->val == cur->next->next->val) {
int x = cur->next->val;
while (cur->next && cur->next->val == x) {
cur->next = cur->next->next;
}
}
else {
cur = cur->next;
}
}
return dummy->next;
}
};
解法大致一致,这种题也没有别的好方法,一般方法就是这种双指针。
但是它这个在空间上更优一点,它不是用两个相邻的慢指针,而是只用左边的慢指针,用到右边慢指针的时候都用next调用。