Տրված կապակցված ցուցակի վերջից ջնջեք N- րդ հանգույցը  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon Արսիսիում Փաստեր Intuit Zoho
Կապված ցուցակ

Խնդիրի հայտարարություն  

«Տրված կապակցված ցուցակի վերջից N n հանգույցը ջնջելու» խնդրով նշվում է, որ ձեզ տրվում է կապված հանգույց ՝ որոշ հանգույցներով: Եվ հիմա դուք պետք է հեռացնեք nth հանգույցը կապված ցուցակի վերջից:

Օրինակ  

Տրված կապակցված ցուցակի վերջից ջնջեք N- րդ հանգույցըPin

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

Բացատրություն. Վերջից 2-րդ հանգույցը 6. է, այնպես որ մենք այն կջնջենք: Եվ հանգույցը ջնջելուց հետո մեզ մնում է ելքում ցույց տրված կապակցված ցուցակը:

Մոտեցում  

Կապված ցուցակը տվյալների գծային կառուցվածք է, որն օգտվում է ցուցիչներից: Եվ սա մեզ խնայում է մեծ հաշվարկային ջանքեր `լրացուցիչ տարրեր ավելացնելու զանգվածի նկատմամբ: Այժմ խնդիրն այն է, որ nth հանգույցը հանվի կապված ցուցակից: Այստեղ ես ձեզ պետք է ասեմ, որ ձեզ տրամադրված չէ կապակցված ցուցակում գտնվող հանգույցների քանակը: Այսպիսով, ի՞նչ մոտեցում պետք է ընտրվի խնդիրը լուծելու համար: Երբ մենք պետք է ջնջենք nth հանգույցը կապված ցուցակի վերջից:

Միամիտ մոտեցում

Միամիտ մոտեցում կլինի նախ կապակցված ցուցակի երկարության հաշվարկը կամ հաշվարկը: Այս եղանակից պահանջվում է, որ մենք նախ մի օղակ աշխատենք մինչև կապակցված ցուցակի ավարտը: Բայց ինչպե՞ս կապակցված ցուցակի հաշվարկը կօգնի 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

Java կոդ ՝ տրված կապակցված ցուցակի վերջից N-րդ հանգույցը ջնջելու համար

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

Բարդության վերլուծություն  

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք անցել ենք ամբողջ կապակցված ցուցակի միջով, ինչը կարժենա մեզ գծային ժամանակի բարդություն:

Տես նաեւ,
Հակադարձ հանգույցներ K-Group- ում

Տիեզերական բարդություն

O (1), քանի որ մենք պարզապես պահեցինք որոշ հաստատուն փոփոխականներ, պահանջվող տարածության բարդությունը հաստատուն է: