ఇచ్చిన లింక్ జాబితా చివరి నుండి Nth నోడ్‌ను తొలగించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆర్సెసియం ఫాక్ట్‌సెట్ Intuit జోహో
లింక్డ్-జాబితా

సమస్యల నివేదిక

“ఇచ్చిన లింక్ జాబితా చివరి నుండి Nth నోడ్‌ను తొలగించు” సమస్య మీకు కొన్ని నోడ్‌లతో లింక్డ్ లిస్ట్ ఇవ్వబడిందని పేర్కొంది. ఇప్పుడు మీరు లింక్ చేసిన జాబితా చివరి నుండి n వ నోడ్‌ను తొలగించాలి.

ఉదాహరణ

ఇచ్చిన లింక్ జాబితా చివరి నుండి Nth నోడ్‌ను తొలగించండి

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

వివరణ: చివరి నుండి 2 వ నోడ్ 6 కాబట్టి మేము దానిని తొలగిస్తాము. మరియు నోడ్ను తొలగించిన తరువాత అవుట్పుట్లో చూపిన లింక్ జాబితాతో మిగిలిపోతాము.

అప్రోచ్

లింక్డ్ లిస్ట్ అనేది పాయింటర్ల ప్రయోజనాన్ని పొందే సరళ డేటా నిర్మాణం. మరియు ఇది అదనపు అంశాలను జోడించే శ్రేణిపై గొప్ప గణన ప్రయత్నాన్ని ఆదా చేస్తుంది. లింక్ చేయబడిన జాబితా నుండి n వ నోడ్‌ను తొలగించడం ఇప్పుడు సమస్య. లింక్ చేయబడిన జాబితాలోని నోడ్‌ల సంఖ్య మీకు అందించబడలేదని ఇక్కడ నేను మీకు చెప్పాలి. కాబట్టి సమస్యను పరిష్కరించడానికి ఏ విధానాన్ని ఎంచుకోవాలి? మేము లింక్ చేసిన జాబితా చివరి నుండి n వ నోడ్‌ను తొలగించాల్సిన అవసరం వచ్చినప్పుడు.

అమాయక విధానం

లింక్ చేయబడిన జాబితా యొక్క పొడవును మొదట లెక్కించడం లేదా లెక్కించడం ఒక అమాయక విధానం. ఈ విధంగా మనకు మొదట లింక్ జాబితా ముగిసే వరకు లూప్‌ను అమలు చేయాలి. లింక్ చేసిన జాబితా యొక్క లెక్కింపు చివరి నుండి n వ నోడ్‌ను తొలగించడంలో ఎలా సహాయపడుతుంది? సమస్యను పరిష్కరించడానికి మేము మొదట లింక్ చేసిన జాబితా యొక్క పొడవును లెక్కిస్తాము. అప్పుడు మేము ఇచ్చిన ఇన్పుట్ ని పొడవు నుండి తీసివేస్తాము. ఇప్పుడు మేము సరళంగా చేస్తాము నోడ్ తొలగించండి తల నుండి పొడవు- n దూరం వద్ద.

ఆప్టిమైజ్ చేసిన విధానం

లింక్ చేయబడిన జాబితా పరిమాణాన్ని లెక్కించకుండా ఆప్టిమైజ్ చేసిన విధానం ఉంటుంది. ఈ సమస్యను పరిష్కరించడానికి ఒక ఉపాయం ఉంది. మొదట, మేము ప్రారంభం నుండి n వ నోడ్ వరకు తలగా ప్రారంభించబడిన నోడ్ను దాటుతాము. ఇప్పుడు మనం ప్రారంభ నోడ్ (తల) నుండి n కి సమానమైన దూరంలో ఉన్న నోడ్ వద్ద నిలబడి ఉన్నాము. అప్పుడు మేము తలకు సమానమైన కొత్త వేరియబుల్‌ను ప్రారంభిస్తాము. మొదటి నోడ్ లింక్డ్ జాబితా యొక్క చివరి నోడ్‌కు చేరే వరకు రెండు నోడ్‌లను దాటడం ప్రారంభించండి. ఆ సమయంలో మా రెండవ వేరియబుల్ చివరి నుండి n + 1 వ నోడ్ వద్ద ఉంటుంది. ఇప్పుడు మీరు తదుపరి నోడ్‌ను తీసివేయాలి.

కోడ్

ఇచ్చిన లింక్ జాబితా చివరి నుండి N వ నోడ్‌ను తొలగించడానికి C ++ కోడ్

#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

ఇచ్చిన లింక్ జాబితా చివరి నుండి Nth నోడ్‌ను తొలగించడానికి జావా కోడ్

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), ఎందుకంటే మనం కొన్ని స్థిరమైన వేరియబుల్స్ ని నిల్వ చేసాము, అవసరమైన స్థలం సంక్లిష్టత స్థిరంగా ఉంటుంది.