C++中从已排序列表中删除重复项

假设我们有一个包含一些元素的列表。我们必须删除所有出现不止一次的元素。因此，列表中只保留不同的元素。如果列表类似于[1,1,1,2,2,3,5,6,6,7,8]，则输出将为[3,5,7,8]，所有其他元素都出现不止一次。

让我们看看步骤 -

  • 创建一个值为-1的虚拟节点，prev := NULL，dummyPtr := dummy
  • 当head不为空时
    • 如果head的下一个节点存在，或者head的值与下一个节点的值不同，则
      • dummyPtr的下一个节点 := head
      • temp := head的下一个节点，并将head的下一个节点设为空
      • head := temp
      • dummyPtr := dummyPtr的下一个节点
    • 否则
      • prev := head，head := head的下一个节点
      • 当head不为空且head的值等于prev的值时
        • prev := head，head := head的下一个节点
  • 返回dummy的下一个节点

让我们看看下面的实现，以便更好地理解 -

示例

　在线演示

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
      int val;
      ListNode *next;
      ListNode(int data){
         val = data;
         next = NULL;
      }
   };
   ListNode *make_list(vector<int> v){
      ListNode *head = new ListNode(v[0]);
      for(int i = 1; i<v.size(); i++){
         ListNode *ptr = head;
         while(ptr->next != NULL){
            ptr = ptr->next;
         }
         ptr->next = new ListNode(v[i]);
      }
      return head;
   }
   void print_list(ListNode *head){
      ListNode *ptr = head;
      cout << "[";
      while(ptr){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* deleteDuplicates(ListNode* head) {
      ListNode* dummy = new ListNode(-1);
      ListNode* prev = NULL;
      ListNode* dummyPtr = dummy;
      ListNode* nextNode;
      while(head){
         if(!head->next || head->val != head->next->val){
            dummyPtr->next = head;
            ListNode* temp = head->next;
            head->next = NULL;
            head = temp;
            dummyPtr = dummyPtr->next;
         } else {
            prev = head;
            head = head->next;
            while(head && head->val == prev->val){
               prev = head;
               head = head->next;
            }
         }
      }
   return dummy->next;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1,2,2,3,5,6,6,7,8};
   ListNode *head = make_list(v);
   print_list(ob.deleteDuplicates(head));
}

输入

[1,1,1,2,2,3,5,6,6,7,8]

输出

[3, 5, 7, 8, ]

更新于：2020年5月4日

241 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习
广告