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

题目

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

思路

首先再原有的链表前面插入一个新的节点，可以减少头指针变化。若 cur->next->val == cur->next->next->val 则删除 cur->next,然后依次判断，将所有重复的节点全部删除。

题解

• 题解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 == nullptr || head->next == nullptr) 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;
    }
};

• 时间复杂度：O(n)，其中 n 是链表中节点的个数，最多遍历一遍链表
• 空间复杂度：O(n)，使用新的链表进行遍历

执行用时：4 ms, 在所有 C++ 提交中击败了92.06%的用户

内存消耗：10.8 MB, 在所有 C++ 提交中击败了65.46%的用户

通过测试用例：166 / 166