Премахване на дубликати от Сортиран списък II


Ниво на трудност M
Често задавани в Амазонка
Свързан списък

Проблемът „Премахване на дубликати от Сортиран списък II“ гласи, че ви е даден свързан списък, който може или не може да има дублиращи се елементи. Ако списъкът има дублирани елементи, премахнете всичките им екземпляри от списъка. След като изпълните следните операции, отпечатайте свързания списък в края.

Пример

Премахване на дубликати от Сортиран списък II

Elements of linked list: 1 2 2 2 3 5 7 7
List after removing all the elements: 1 3 5

Обяснение

Числото 2 има 3 случая в списъка. По този начин премахнахме всички негови случаи. Същото се случи и с номер 7. Така че след премахване на всички екземпляри от 2 и 7. Остават ни само 3 елемента, които са 1 3 5.

Подход

Проблемът „Премахване на дубликати от сортиран списък II“, както вече беше посочено, ни изисква да премахнем всички числа, които имат дубликати в списъка. Веднъж имаше обсъден проблем. Но има малка разлика в настоящия проблем. По-ранният проблем ни помоли изтрийте само дубликатите. Това означава, че изтрихме дубликатите, но едно копие на елемента, чиито дубликати присъстваха, не беше премахнато. Тук трябва да изтрием всяко копие и оригиналния елемент, който има дубликати в списъка.

И така, сега сме запознати с проблема. Можем да измислим начини за справяне с проблема. Вече знаем, че списъкът е сортиран. Така че можем да използваме този факт. Ако списъкът е сортиран, сме сигурни, че ако има дубликат. Те винаги се срещат в група. И така, просто трябва да проверим съседните елементи за дубликати. Ако попаднем на такава двойка. Първо, обхождаме списъка, докато не намерим недублиращ се елемент или списъкът свърши. В този момент насочваме предишния възел към този нов недублиращ се елемент. След това отново започнете да търсите дублиращи се елементи от този недублиращ се елемент.

Под термина „недублиращ се“ нямаме предвид, че текущият елемент няма дубликати в списъка. Това просто означава, че текущият възел не е равен на този елемент. Помислете, имаме 1, 2, 2, 2, 3, 3 в списъка. Посочваме 1 към 3. Въпреки това, 3 също ще бъдат премахнати. Но в даден момент, когато проверявахме за съседни елементи и попаднахме на първите 2 2 двойки. Казваме, че 3 не е дубликат, защото не е 2.

Така че, за да обобщим това. Ние просто прекосяваме списъка. И продължавайте да проверявате дали следващият елемент е същият като този на текущия елемент. Ако това се случи, продължете да премахвате елементи, докато намерите недублиращ се елемент.

код

C ++ код за премахване на дубликати от сортиран списък II

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

ListNode* deleteDuplicates(ListNode* head) {
    if(head==NULL || head->next==NULL)
        return head;
    ListNode* prev = create(-1);
    ListNode* dummy = prev;
    ListNode* cur = head;
    prev->next = cur;
    while(cur && cur->next) {
        if(cur->data == cur->next->data) {
            while(cur->next && cur->data==cur->next->data) {
                ListNode* tmp = cur;
                cur = cur->next;
                free(tmp);
            }
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy->next;
}

void printLinkedList(ListNode *headA){
  while(headA != NULL){
    cout<<headA->data<<" ";
    headA = headA->next;
  }
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  headA->next->next = create(2);
  headA->next->next->next = create(2);
  headA->next->next->next->next = create(3);
  headA->next->next->next->next->next = create(5);
  headA->next->next->next->next->next->next = create(7);
  headA->next->next->next->next->next->next->next = create(7);

  headA = deleteDuplicates(headA);
  printLinkedList(headA);
}
1 3 5

Java код за премахване на дубликати от сортиран списък II

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

  static ListNode deleteDuplicates(ListNode head) {
      if(head==null || head.next==null)
          return head;
      ListNode prev = create(-1);
      ListNode dummy = prev;
      ListNode cur = head;
      prev.next = cur;
      while(cur != null && cur.next != null) {
          if(cur.data == cur.next.data) {
              while(cur.next != null && cur.data==cur.next.data) {
                  ListNode tmp = cur;
                  cur = cur.next;
              }
              prev.next = cur.next;
              cur = prev.next;
          } else {
              prev = cur;
              cur = cur.next;
          }
      }
      return dummy.next;
  }

  static void printLinkedList(ListNode headA){
    while(headA != null){
      System.out.print(headA.data+" ");
      headA = headA.next;
    }
  }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    headA.next.next = create(2);
    headA.next.next.next = create(2);
    headA.next.next.next.next = create(3);
    headA.next.next.next.next.next = create(5);
    headA.next.next.next.next.next.next = create(7);
    headA.next.next.next.next.next.next.next = create(7);

    headA = deleteDuplicates(headA);
    printLinkedList(headA);
  }
}
1 3 5

Анализ на сложността

Сложност във времето

НА), защото обхождаме елементите точно един. По този начин сложността на времето е линейна.

Сложност на пространството

O (1), защото сме използвали константни елементи. Така космическата сложност е постоянна.