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


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन आर्सेसियम फॅक्टसेट अंतर्ज्ञानाने जाणणे Zoho
दुवा साधलेली यादी

समस्या विधान  

“दिलेल्या लिंकच्या यादीच्या शेवटी एनटी नोड डिलीट करा” ही समस्या सांगते की आपल्याला काही नोड्ससह दुवा साधलेली यादी दिली आहे. आणि आता आपल्याला दुवा साधलेल्या सूचीच्या शेवटी नॅव्हे नोड काढण्याची आवश्यकता आहे.

उदाहरण  

दिलेल्या दुवा साधलेल्या सूचीच्या शेवटी नॅथ नोड हटवापिन

2->3->4->5->6->7
delete 3rd node from last
2->3->4->6->7

स्पष्टीकरणः शेवटचा दुसरा नोड is आहे त्यामुळे आपण ते डिलीट करू. आणि नोड डिलीट केल्यावर आऊटपुट मध्ये दर्शविलेल्या लिंक्ड लिस्ट बरोबर उरते

दृष्टीकोन  

दुवा साधलेली यादी ही एक रेषीय डेटा रचना आहे जी पॉईंटर्सचा लाभ घेते. आणि हे आमच्यासाठी अतिरिक्त घटक जोडण्याच्या मोठ्या संख्येने संगणकीय प्रयत्नास वाचवते. आता समस्या म्हणजे दुवा साधलेल्या सूचीतून नवा नोड काढण्याची. येथे मी सांगेन की आपणास दुवा साधलेल्या यादीतील नोडची संख्या पुरविली जात नाही. तर समस्येचे निराकरण करण्यासाठी एखाद्याने कोणता दृष्टीकोन निवडला पाहिजे? जेव्हा आम्हाला दुवा साधलेल्या सूचीच्या शेवटी नवा नोड हटविणे आवश्यक आहे.

भोळे दृष्टिकोन

एक भोळसट दृष्टिकोन म्हणजे प्रथम दुवा साधलेल्या सूचीची लांबी गणना करणे किंवा गणना करणे. या मार्गाने आम्हाला दुवा साधलेल्या सूचीच्या समाप्तीपर्यंत प्रथम लूप चालविणे आवश्यक आहे. परंतु दुवा साधलेल्या यादीची गणना शेवटपासून एनडी नोड काढण्यात कशी मदत करेल? समस्येचे निराकरण करण्यासाठी आम्ही प्रथम दुवा साधलेल्या सूचीच्या लांबीची गणना करू. नंतर दिलेल्या इनपुट लांबीपासून वजा करू. आता आपण सहजपणे करू नोड हटवा डोके पासून लांबी-एन अंतरावर.

हे सुद्धा पहा
ग्राफ क्लोनिंग

ऑप्टिमाइझ केलेला दृष्टीकोन

लिंक्ड सूचीच्या आकाराची गणना केल्याशिवाय एक ऑप्टिमाइझ केलेला दृष्टीकोन असेल. ही समस्या सोडविण्याची युक्ती आहे. प्रथम, आम्ही सुरूवातीपासून एनडी नोड होईपर्यंत डोके म्हणून आरंभ केलेला एक नोड ट्रॅव्हर्स करतो. आता आम्ही स्टार्ट नोड (हेड) पासून n च्या समान अंतरावर असलेल्या नोडवर उभे आहोत. नंतर आपण हेड व्हेरिएबल बरोबर व्हेरिएबल प्रारंभ करू. त्यानंतर प्रथम नोड दुवा साधलेल्या सूचीच्या शेवटच्या नोडपर्यंत पोहोचेपर्यंत दोन्ही नोडचा शोध घेणे सुरू करा. त्यावेळी आमचा दुसरा व्हेरिएबल शेवटपासून n + 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;
}

node* deleteNthNodeFromLast(node* head, int n){
    // first move ahead n nodes
    // then start traversing from the start until the end node
    // delete the temporary node
    node* cur = head;
    while(n--){
        cur = cur->next;
        if(!cur){
            cur = head;
            head = head->next;
            free(cur);
            return head;
        }
    }
    node* tmp = head;
    while(cur->next){
        tmp = tmp->next;
        cur = cur->next;
    }
    cur = tmp->next;
    tmp->next = tmp->next->next;
    return head;
}

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;
  }
  head = deleteNthNodeFromLast(head, 3);

  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 4 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 deleteNthNodeFromLast(node head, int n){
        // first move ahead n nodes
        // then start traversing from the start until the end node
        // delete the temporary node
        node cur = head;
        while(n-- > 0){
            cur = cur.next;
            if(cur == null){
                cur = head;
                head = head.next;
                return head;
            }
        }
        node tmp = head;
        while(cur.next != null){
            tmp = tmp.next;
            cur = cur.next;
        }
        cur = tmp.next;
        tmp.next = tmp.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);
        head.next.next = create(4);
        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 = deleteNthNodeFromLast(head, 3);

        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 4 6 7

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

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

ओ (एन), कारण आम्ही संपूर्ण दुवा साधलेल्या यादीतून पुढे गेलो आहोत ज्यामुळे आम्हाला रेषेत वेळ गुंतागुंत होते.

हे सुद्धा पहा
के-ग्रुपमधील रिव्हर्स नोड्स

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

ओ (1), कारण आम्ही नुकतीच काही स्थिर व्हेरिएबल्स संग्रहित केली आहेत. आवश्यक असलेली जागा अवघड आहे.