LeetCode题解合集
题目描述
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
题解:
双指针。
写法一:
使用快慢指针 fast
和 low
, low
指向无重复元素链表最后一个元素,根据 fast
和 low
指向的值是否相等来判断节点该不该加入到结果中去。
时间复杂:$O(n)$
额外空间复杂度:$O(1)$
/**
* 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) {
if ( !head || !head->next ) return head;
ListNode *dummy = new ListNode;
dummy->next = head;
ListNode *fast = head, *low = head, *pre = dummy;
while ( low ) {
if( !low->next ) break;
fast = low->next;
if ( fast->val != low->val ) {
pre->next = low;
pre = low;
}
while ( fast && fast->val == low->val )
fast = fast->next;
low = fast;
}
pre->next = low ? low : nullptr;
return dummy->next;
}
};
/*
时间:8ms,击败:88.88%
内存:10.8MB,击败:28.13%
*/
写法二:
上述写法中使用了三个指针,也可以用两个指针。
/**
* 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) {
if ( !head || !head->next ) return head;
ListNode *dummy = new ListNode;
dummy->next = head;
ListNode *now = head, *pre = dummy;
while ( now ) {
if ( now->next && now->next->val == now->val ) {
while ( now->next && now->next->val == now->val )
now = now->next;
pre->next = now->next;
} else pre = now;
now = now->next;
}
return dummy->next;
}
};
/*
时间:4ms,击败:99.19%
内存:10.9MB,击败:23.97%
*/