डोके निर्देशकाशिवाय दुवा साधलेल्या सूचीतून नोड हटवा  


अडचण पातळी सोपे
वारंवार विचारले जीई हेल्थकेअर एमक्यू
दुवा साधलेली यादी टेक्निकल स्क्रिप्ट

समस्या विधान  

"हेड पॉइंटरशिवाय दुवा साधलेल्या सूचीतून नोड हटवा" ही समस्या सांगते की आपल्याकडे काही नोड्ससह दुवा साधलेली यादी आहे. आता आपल्याला एक नोड हटवायचा आहे परंतु आपल्याकडे त्याचा मूळ नोड पत्ता नाही. तर हे नोड हटवा.

उदाहरण  

डोके निर्देशकाशिवाय दुवा साधलेल्या सूचीतून नोड हटवा

2->3->4->5->6->7
Node to be deleted: 4
2->3->5->6->7

स्पष्टीकरणः आम्हाला 4 मूल्यासह नोड हटवायचे असल्याने आम्ही ते दुवा साधलेल्या सूचीतून काढून टाकले आहे आणि आउटपुटमध्ये नमूद केलेल्या यादीसह बाकी आहे.

हेड पॉईंटरशिवाय नोड हटविण्याचा दृष्टीकोन  

दुवा साधलेली सूची ही एक रेषीय डेटा रचना आहे ज्याचा अ‍ॅरेवर मोठा फायदा आहे तो आकारात बदलू शकतो. आपण दुवा साधलेल्या यादीमध्ये घटक जोडू इच्छित असल्यास आपण हे ओ (1) वेळेत जोडू शकता. आपण प्रथम ठिकाणी घटक घालत आहात हे लक्षात घेऊन. परंतु आपल्याला सामान्य अ‍ॅरेमध्ये असेच करायचे असल्यास. हे करण्यासाठी आपल्यास ओ (एन) वेळ लागेल. अशा प्रकारे वास्तवीक अनुप्रयोगांमध्ये अ‍ॅरेवर दुवा साधलेली यादी वापरणे अनुकूल आहे. आणि लिंक्ड यादी या सर्वांना प्राप्त करते कारण ती एक संक्षिप्त भाग म्हणून डेटा संग्रहित करत नाही. हे प्रत्येक घटक काही यादृच्छिक ठिकाणी संग्रहित करते. पण मग ते ऑर्डर कशी ठेवेल? या प्रश्नाचे उत्तर असे आहे की, जोडलेली यादी पॉईन्टरचा वापर करते. प्रत्येक नोड लिंक्ड यादीतील दुसर्‍या नोडकडे निर्देश करतो आणि या मार्गाने आपल्याला एकच भाग बदलून देण्याची गरज नाही ज्यायोगे बरीच गणना करणे आवश्यक असते.

हे सुद्धा पहा
के क्रमवारीबद्ध दुवा यादी विलीन करा

जर हेड पॉईंटर दिले असेल

आता समस्या आम्हाला विचारते नोड हटवा. साधारणपणे, आम्हाला नोडचा पत्ता देण्यात येतो आणि दुवा साधलेल्या सूचीत पुढील नोड हटविणे आवश्यक असते. परंतु येथे आम्हाला एक नोड हटविणे आवश्यक आहे ज्याचा पत्ता आम्हाला देण्यात आला आहे. या समस्येचे निराकरण करण्याचा एक मार्ग म्हणजे प्रथम संपूर्ण दुवा साधलेल्या सूचीतून पुढे जाणे. नंतर प्रत्येक नोडचा पालक संचयित करा आणि आपण इनपुट म्हणून प्रदान केलेल्या नोडवर असता तेव्हा लूप तोडू. या मार्गाने शेवटी नोडचे मूळ पालक हटविले जातील. तर आता समस्या ज्याच्या पालकांचा पत्ता दिलेली आहे त्या लिंकच्या नोडच्या साध्या हटविण्यापर्यंत बदलली आहे. परंतु हे केल्याने आम्हाला ओ (एन) ऑपरेशन खर्च करावे लागतील. परंतु जेव्हा आपल्याकडे हेड पॉईंटर असेल तेव्हाच हा मार्ग वापरला जाऊ शकतो.

उपाय

"हेड पॉईंटरशिवाय दुवा साधलेल्या सूचीतून नोड हटवा" या समस्येचा दृष्टीकोन म्हणजे हटविल्या जाणार्‍या नोडचा डेटा आणि दुवा साधलेल्या यादीतील पुढील नोड स्वॅप करणे होय. दुवा साधलेल्या सूचीतील प्रत्येक नोड पुढील स्टोअरमध्ये आहे. तर या ऑपरेशनमध्ये केवळ ओ (1) वेळची जटिलता आहे. आता जेव्हा डेटा स्वॅप केला जाईल. पुन्हा, आम्ही ज्याच्या पालकांचा पत्ता दिला आहे तो नोड हटविण्यासाठी समस्या बदलली आहेत. तर आता आपल्यासाठी ही समस्या सोडवणे सोपे आहे. जेव्हा आम्हाला शेवटचे नोड हटवायचे असते तेव्हा एक किनार आहे परंतु आम्ही ते हटवू शकणार नाही. कारण पुढे कोणताही नोड नाही.

हे सुद्धा पहा
किमान व जास्तीत जास्त वेतन लीटकोड सोल्यूशन वगळता सरासरी वेतन

कोड  

मुख्य पॉइंटरशिवाय नोड हटविण्यासाठी सी ++ कोड

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

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

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

void deletedNode(node* &head, node* toBeDeleted){
  if(toBeDeleted == NULL)
    return;
  else{
    if(toBeDeleted->next == NULL){
      cout<<"Last node can't be freed";
    }
    // store or swap but ( the data of current node will be deleted)
    toBeDeleted->data = toBeDeleted->next->data;
    toBeDeleted->next = toBeDeleted->next->next;
  }
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  deletedNode(head, toBeDeleted);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}
Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 5 6 7

हेड पॉइंटरशिवाय नोड हटविण्यासाठी जावा कोड

import java.util.*;
class node{
  int data;
  node next;
}
 
class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.next = null;
    return tmp;
  }
 
  static node deletedNode(node head, node toBeDeleted){
    if(toBeDeleted == null)
      return null;
    else{
      if(toBeDeleted.next == null){
        System.out.print("Last node can't be freed");
        return null;
      }
      // store or swap but ( the data of current node will be deleted)
      toBeDeleted.data = toBeDeleted.next.data;
      toBeDeleted.next = toBeDeleted.next.next;
      return head;
    }
  }
 
  public static void main(String[] args){
    // create a linked list
    node head = new node();
    head = create(2);
    head.next = create(3);
    node toBeDeleted = create(4);
    head.next.next = toBeDeleted;
    head.next.next.next = create(5);
    head.next.next.next.next = create(6);
    head.next.next.next.next.next = create(7);
 
    System.out.print("Old Linked List: ");
    node tmp = head;
    while(tmp != null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
    head = deletedNode(head, toBeDeleted);
 
    System.out.print("\n"+"New Linked List: ");
    tmp = head;
    while(tmp!=null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
  }
}
Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 5 6 7

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (1), कारण अदलाबदल सतत चालू ठेवता येते. आणि मग आम्ही फक्त काही पॉइंटर्स बदलतो जे पुन्हा सतत टाईम ऑपरेशन असतात.

हे सुद्धा पहा
दुवा साधलेली यादी उलट करा

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आपण वापरलेले व्हेरिएबल्स लिंक्ड लिस्टमधील नोड्सच्या संख्येवर अवलंबून नाहीत. अशा प्रकारे जागेची जटिलता देखील स्थिर आहे.