Leetcode83. 删除排序链表中的重复元素

2021年5月10日 138Browse 1Like 0Comments

题目描述

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次

返回同样按升序排列的结果链表。

示例 1:

img

输入:head = [1,1,2]
输出:[1,2]

示例 2:

img

输入: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)$

agedcat_xuanzai

这个人很懒,什么都没留下

Comments