题目描述
存在一个按升序排列的链表,给你这个链表的头节点 head
,请你删除所有重复的元素,使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1:
输入:head = [1,1,2]
输出:[1,2]
示例 2:
输入:head = [1,1,2,3,3]
输出:[1,2,3]
提示:
- 链表中节点数目在范围
[0, 300]
内 -100 <= Node.val <= 100
- 题目数据保证链表已经按升序排列
解题思路
这道题的思路比较简单。只需要注意在记录指向当前结点的指针的同时,还需要记录指向上一个结点的指针,在当前结点与下一个结点元素相同的时候,将当前节点删除。
这个方法智能运用于有序链表,如果是无序链表中删除重复元素,就需要用哈希表来记录元素出现的次数或者标记是否出现。
示例代码
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) {}
};
ListNode* deleteDuplicates(ListNode* head)
{
if(head==nullptr||head->next==nullptr) return head;
ListNode* virtualHead=new ListNode(-1,head);
ListNode* pre=virtualHead;
ListNode* cur=pre->next;
while(cur->next!=nullptr)
{
if(cur->next->val==cur->val)
{
pre->next=cur->next;
cur=pre->next;
continue;
}
cur=cur->next;
pre=pre->next;
}
return virtualHead->next;
}
时间复杂度:$O(n)$
空间复杂度:$O(1)$
文章评论