跳转至

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

leetcode

思路

题意分析

题目说的删除重复元素,并不是简单的「去重」,而是将「重复的元素都删掉」

picture 0

如上示例1,值为3的元素重复了两次,值为4的元素重复了两次,于是将所有值为3和4的元素都删除

而不是分别留下一个值为3的元素和值为4的元素

删除重复元素

如果不考虑内存释放

ListNode* nextNode = prevNode->next->next;
prevNode->next = nextNode;

删除链表元素的方法我们应该已经知道,需要找到targetNode的前一个节点prevNode和后一个节点nextNode,如果不考虑内存释放,甚至不需要考虑targetNode

将这个思路延伸到本题,我们想要删除的不再是一个节点,而是「一连串」节点(由于题目给出了「升序」,因此删除的元素一定是连续的)

如果将这一连串的节点当作一个节点,应用我们之前的思路: - targetNode就是这一连串节点 - prevNode就是在过去遍历中不重复链表的最后一个节点 - nextNode就是未遍历链表的第一个节点

Solution

遍历链表,使用哈希表记录每个值对应的元素出现次数

遍历链表后,根据哈希表结果,将出现次数为1的元素按照值从小到大串联为新的已排序链表

唯一难点:STL用法

/**
* 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) {}
* };
*/
struct CompareListNode {
    bool operator()(const ListNode* lhs, const ListNode* rhs) const {
        return lhs->val < rhs->val;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        map<ListNode*, int,CompareListNode> hashMap;
        ListNode* p = head;
        while(p != nullptr){
            hashMap[p] += 1;
            p = p->next;
        }
        ListNode* dummyNode = new ListNode(-1);
        ListNode* pp = dummyNode;
        for (auto pair : hashMap) {
            if(pair.second == 1){
                ListNode* ptr = pair.first;
                ptr->next = nullptr;
                pp->next = ptr;
                pp = pp->next;
            }
        }
        return dummyNode->next;
    }
};

由思路分析,我们自然想到快慢指针:

删除重复元素:

  1. 指针fast指向遍历的元素,指针slow指向过去遍历中未重复链表的最后一个节点
  2. 当指针fast遇到重复元素直接跳过,重复这一步骤,直到没有重复元素为止,最后fast指向新的未重复元素
  3. slow指向此时的fast,完成删除

没有重复元素的时候正常遍历即可

/**
* 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) {
        // 防止第一个元素就是要删除的重复元素,引入dummyNode
        // 题意条件为-100 <= Node.val <= 100,所以dummyNode值设为101
        ListNode* dummyNode = new ListNode(101);
        dummyNode->next = head;
        // 定义快慢指针,fast指向遍历的元素,slow指向已遍历的未重复链表的最后一个元素
        ListNode* fast = head;
        ListNode* slow = dummyNode;
        // 遍历原链表,遍历结束的条件是fast == nullptr 
        while(fast != nullptr){
            // 判断是否有重复元素
            // 有重复元素
            if(fast->next != nullptr && fast->val == fast->next->val){
                // 一旦出现重复元素,重复元素可能不只一个,因此使用while
                while(fast->next != nullptr && fast->val == fast->next->val){
                    // 遇到重复元素直接跳过
                    fast = fast->next;
                }
                // 到达这一步时,fast指向重复元素的最后一个,我们需要nextNode
                fast = fast->next;
                // 此时fast为一连串重复元素的nextNode
                // nextNode可能为新的重复元素,因此交给下一次循环继续处理
                // 每次循环只处理相同值的一连串重复元素
            }
            // 没有重复元素
            else{
                slow->next = fast;
                fast = fast->next;
                slow = slow->next;
            }
        }
        // 给链表添上结尾
        slow->next = nullptr;
        return dummyNode->next;
    }
};

与快慢指针删除重复元素不同,我们也可以直接维护两个链表,一个收集未重复元素,一个收集重复元素

/**
* 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) {
        // 创建两个链表,一个收集未重复元素,一个收集重复元素
        // 题意条件为-100 <= Node.val <= 100,所以dummyNode值设为101
        ListNode* dummyUniqNode = new ListNode(101);
        ListNode* dummyDupNode = new ListNode(101);
        ListNode* p1 = dummyUniqNode;
        ListNode* p2 = dummyDupNode;
        // 遍历原链表
        while(head != nullptr){
            // 重复元素判断有两种情况:
            // 情况1: head->next != nullptr && head->val == head->next->val说明当前元素和下一个元素重复
            // 情况2: 如果情况1失效,说明head到达一连串重复元素的最后一个元素,此时需要和已收集重复元素的最后一个元素比较
            // 因此情况2条件为head->val == p2->val
            if((head->next != nullptr && head->val == head->next->val) || head->val == p2->val){
                p2->next = head;
                p2 = p2->next;
            }
            // 未重复元素正常收集即可
            else{
                p1->next = head;
                p1 = p1->next;
            }
            head = head->next;
        }
        // 记得给链表末尾添上nullptr
        p1->next = nullptr;
        p2->next = nullptr;
        return dummyUniqNode->next;
    }
};

由思路分析和快慢指针解法分析可得出如下重复步骤:

  1. 从未遍历链表中找出第一个元素fast和它的下一个元素fast->next
  2. 比较两者大小是否相同
  3. 如果相同,则重复步骤1和步骤2。重复停止时,这时我们遍历的是重复元素的最后一个元素,找到其下一个元素,接着重复步骤1到3
  4. 如果不相同,更新不重复链表slow->next = fast; slow = slow->next

递归参数: 未遍历链表的头节点head 递归返回值: 已排序且去掉重复元素的链表头 递归终止条件:第一个元素fast和它的下一个元素fast->next都为空

简单来说,递归做的事情只有一个:每次递归只去除一个值对应的多个重复元素

  1. 从未遍历的链表中找到同一个值重复的元素,去除重复的元素。
  2. 重复步骤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;
        // 没有重复元素
        if(head->val == head->next->val){
            head->next = deleteDuplicates(head->next);
            return head;
        }
        // 有重复元素
        while(head->next != nullptr && head->val == head->next->val){
            head = head->next;
        }
        // 去除多余的重复元素,此时head指向最后一个重复元素
        // head->next为新的未遍历链表的头节点
        return deleteDuplicates(head->next);
    }
};