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

题目描述

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

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

示例 1：

img

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

示例 2：

img

1
2
输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列

解题思路

这道题的思路比较简单。只需要注意在记录指向当前结点的指针的同时，还需要记录指向上一个结点的指针，在当前结点与下一个结点元素相同的时候，将当前节点删除。

这个方法智能运用于有序链表，如果是无序链表中删除重复元素，就需要用哈希表来记录元素出现的次数或者标记是否出现。

示例代码

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
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(n)

空间复杂度：O(1)O(1)