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

假设我们有一个排序的链表;我们必须删除所有重复项,以便每个元素仅出现一次。

因此,如果输入类似于[1,1,2,3,3,3,4,5,5],那么输出将为[1,2,3,4,5]

为了解决这个问题,我们将遵循以下步骤-

  • dummy:=使用值-inf创建一个新节点

  • 下一个假人:=头

  • curr =虚拟

  • 当curr不为零时,执行-

    • 下一个:=下一个下一个

    • 下一个=当前的下一个

    • while(next不为null,next的val与curr的val相同)时,执行-

    • 下一个curr:= next

    • curr:=下一个

    • 返回假人的下一个

    示例

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

    #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(INT_MIN);
          dummy->next = head;
          ListNode * curr = dummy;
          while(curr){
             ListNode * next = curr->next;
             while(next && next->val==curr->val)
                next = next->next;
             curr->next = next;
             curr=next;
          }
          return dummy->next;
       }
    };
    main(){
       Solution ob;
       vector<int> v = {1,1,2,3,3,3,4,5,5};
       ListNode *head = make_list(v);
       print_list(ob.deleteDuplicates(head));
    }

    输入值

    {1,1,2,3,3,3,4,5,5}

    输出结果

    [1, 2, 3, 4, 5, ]