LeetCode

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

nkul · 9月7日 · 2020年 46次已读
  • 需要虚拟头结点(dummy)
  • 从dummy下一节点开始找区间,使用双指针法:
    • a指向dummy->next,b=a->next
    • 当b的值和a的值相同,b后移
    • 最终形成[a,b)区间
  • 判断重复的方法:
    • b = a->next,说明a和它下一节点不同,这样a不会重复,不用删除
    • 否则,b之前都是a重复出现,dummy->next = b,删除b之前重复内容!
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto  p = dummy;
        while(p->next){
            auto q = p->next->next;
            //双指针找到左闭右开的重复区间
            while(q && q->val == p->next->val) q = q->next;
            //相邻,说明没有重复,指针后移
            if(p->next->next == q) p = p->next;
            //否则删除
            else p->next = q;
        }

        return dummy->next;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!