સ Sર્ટ કરેલી સૂચિ II માંથી ડુપ્લિકેટ્સ દૂર કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન
લિંક્ડ-સૂચિ

સમસ્યા "સ Sર્ટ કરેલી સૂચિ II માંથી ડુપ્લિકેટ્સને દૂર કરો" જણાવે છે કે તમને એક લિંક્ડ સૂચિ આપવામાં આવી છે જેમાં ડુપ્લિકેટ તત્વો હોઈ શકે છે અથવા નહીં. જો સૂચિમાં ડુપ્લિકેટ તત્વો છે, તો પછી તેમના બધા દાખલાઓને સૂચિમાંથી દૂર કરો. નીચે આપેલ કામગીરી કર્યા પછી, કડી થયેલ સૂચિને અંતે છાપો.

ઉદાહરણ

સ Sર્ટ કરેલી સૂચિ II માંથી ડુપ્લિકેટ્સ દૂર કરો

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

સમજૂતી

નંબર 2 ની સૂચિમાં 3 ઉદાહરણો છે. આમ અમે તેના બધા દાખલા કા removedી નાખ્યા. Number નંબર સાથે આવું જ થયું. તેથી, 7 અને 2. ના બધા દાખલાઓ કા after્યા પછી આપણી પાસે ફક્ત 7 તત્વો જ બાકી છે જે 3 1 3 છે.

અભિગમ

સૂચિમાં હાજર ડુપ્લિકેટ્સ ધરાવતા તમામ નંબરોને હટાવવા માટે પહેલેથી જ જણાવ્યું છે તેમ સમસ્યા "સ Sર્ટ કરેલી સૂચિ II માંથી ડુપ્લિકેટ્સને દૂર કરો" સમસ્યા. એકવાર ચર્ચા કરવામાં સમસ્યા આવી હતી. પરંતુ હાલની સમસ્યામાં થોડો તફાવત છે. પહેલાંની સમસ્યાએ અમને કહ્યું ફક્ત ડુપ્લિકેટ્સ કા deleteી નાખો. તે જ છે કે અમે ડુપ્લિકેટ્સ કા deletedી નાખી છે પરંતુ જે તત્વની ડુપ્લિકેટ્સ હાજર છે તેની એક પણ નકલ દૂર કરવામાં આવી નથી. અહીં આપણે દરેક ક copyપિ અને મૂળ તત્વ કા deleteી નાખવા પડશે જેની સૂચિમાં તેની ડુપ્લિકેટ્સ હતી.

તેથી, હવે આપણે સમસ્યાથી પરિચિત છીએ. આપણે સમસ્યાનો સામનો કરવાની રીતો વિશે વિચારી શકીએ છીએ. આપણે પહેલેથી જ જાણીએ છીએ કે સૂચિને સ .ર્ટ કરવામાં આવી છે. તો આપણે આ તથ્યનો ઉપયોગ કરી શકીએ. જો સૂચિને સortedર્ટ કરવામાં આવી છે, તો અમને ખાતરી છે કે જો ત્યાં કોઈ ડુપ્લિકેટ છે. તેઓ હંમેશાં જૂથમાં થાય છે. તેથી, આપણે ફક્ત ડુપ્લિકેટ્સ માટે અડીને તત્વો તપાસો. જો આપણે આવી જોડી આવે. પ્રથમ, અમે સૂચિને ત્યાં સુધી વટાવીએ છીએ જ્યાં સુધી અમને કોઈ ડુપ્લિકેટ તત્વ ન મળે અથવા સૂચિ સમાપ્ત થાય નહીં. તે સમયે, અમે આ નવા ન -ન-ડુપ્લિકેટ તત્વ તરફના પાછલા નોડને નિર્દેશિત કરીએ છીએ. પછી ફરીથી આ બિન-ડુપ્લિકેટ તત્વમાંથી ડુપ્લિકેટ તત્વોની શોધ શરૂ કરો.

“નોન-ડુપ્લિકેટ” શબ્દ દ્વારા, અમારો અર્થ એ નથી કે વર્તમાન તત્વની સૂચિમાં કોઈ ડુપ્લિકેટ્સ નથી. તેનો માત્ર અર્થ એ છે કે વર્તમાન નોડ આ તત્વ સાથે સમાન નથી. ધ્યાનમાં લો, અમારી પાસે સૂચિમાં 1, 2, 2, 2, 3, 3 છે. અમે 1 થી 3 તરફ નિર્દેશ કરીએ છીએ. જો કે, 3 પણ દૂર કરવામાં આવશે. પરંતુ અમુક સમયે, જ્યારે અમે નજીકના તત્વોની તપાસ કરી રહ્યા હતા અને પ્રથમ 2 2 જોડી મળી. આપણે કહીએ છીએ કે 3 એ ડુપ્લિકેટ છે કારણ કે તે 2 નથી.

તેથી, આનો સારાંશ આપવા માટે. અમે ફક્ત સૂચિને વટાવીએ છીએ. અને તપાસવાનું ચાલુ રાખો કે આગામી તત્વ વર્તમાન તત્વ જેવું જ છે કે કેમ. જો તે થાય છે, તો ત્યાં સુધી તત્વોને દૂર કરવાનું ચાલુ રાખો જ્યાં સુધી તમને બિન-ડુપ્લિકેટ તત્વ ન મળે.

કોડ

સ +ર્ટ કરેલી સૂચિ 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 માંથી ડુપ્લિકેટ્સને દૂર કરવા માટે જાવા કોડ 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), કારણ કે આપણે સતત તત્વોનો ઉપયોગ કર્યો છે. આમ જગ્યા જટિલતા સતત છે.