Κατάργηση διπλότυπων από τη Ταξινομημένη λίστα II


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα
Συνδεδεμένη λίστα

Το πρόβλημα "Κατάργηση διπλότυπων από την ταξινομημένη λίστα 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί διασχίζουμε τα στοιχεία ακριβώς ένα. Έτσι, η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

Ο (1), γιατί έχουμε χρησιμοποιήσει σταθερά στοιχεία. Έτσι, η διαστημική πολυπλοκότητα είναι σταθερή.