Mündəricat
Problem bəyanat
"Nömrəni verilmiş əlaqəli siyahının sonundan sil" problemi sizə bəzi qovşaqlarla əlaqəli bir siyahı verildiyini bildirir. Və indi əlaqəli siyahının sonundan nth nodu silməlisiniz.
misal
2->3->4->5->6->7 delete 3rd node from last
2->3->4->6->7
İzahat: Sondan ikinci qovşaq 2.-dır, buna görə də siləcəyik. Düyünü sildikdən sonra çıxışda göstərilən əlaqəli siyahı qalır.
Yanaşma
Bağlı Siyahı göstəricilərdən faydalanan xətti bir məlumat quruluşudur. Və bu, əlavə elementlər əlavə etmək üçün bizə böyük hesablama səyindən qənaət edir. İndi problem əlaqəli siyahıdan nth nodu qovmaqdır. Burada sizə əlaqəli siyahıda qovşaq sayı ilə təmin edilmədiyini söyləməliyəm. Bəs problemi həll etmək üçün hansı yanaşma seçilməlidir? Bağlı siyahının sonundan n-ci qovluğu silməyimiz lazım olduqda.
Sadəlövh yanaşma
Sadəlövh yanaşma əvvəlcə əlaqəli siyahının uzunluğunu hesablamaq və ya hesablamaq olacaqdır. Bu yolla əvvəlcə əlaqəli siyahının sonuna qədər bir döngü işləməyimiz tələb olunur. Bəs əlaqəli siyahının hesablanması n-düyünün sonundan çıxarılmasına necə kömək edəcək? Problemi həll etmək üçün əvvəlcə əlaqəli siyahının uzunluğunu hesablayacağıq. Sonra verilmiş girişi uzunluqdan çıxardacağıq. İndi sadəcə edəcəyik düyünü silin uzunluqdan-n məsafədən başdan.
Optimallaşdırılmış yanaşma
Optimize edilmiş yanaşma əlaqəli siyahının ölçüsünü hesablamadan olacaqdır. Bu problemi həll etmək üçün bir hiylə var. Əvvəlcə başlanğıcdan n-ci düyünə qədər baş kimi başlanğıc edilmiş bir düyünü keçirik. İndi başlanğıc düyünündən (başdan) n-ə bərabər məsafədə olan bir qovşaqda dayanırıq. Sonra başa bərabər yeni bir dəyişən başlatırıq. Sonra ilk qovşaq əlaqəli siyahının son qovşağına çatana qədər hər iki qovşaqdan keçməyə başlayın. O zaman ikinci dəyişənimiz sondan n + 1-ci qovşaqda olacaq. İndi yalnız növbəti nodu silməlisiniz.
Kodu
Verilən əlaqəli siyahının sonundan Nth nodu silmək üçün C ++ kodu
#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
Verilən əlaqəli siyahının sonunda Nth nodu silmək üçün Java kodu
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
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (N), çünki bizə xətti zaman mürəkkəbliyinə başa gələcək əlaqəli siyahının hamısını keçdik.
Kosmik Mürəkkəblik
O (1), çünki tələb etdiyimiz boşluq mürəkkəbliyi sabit olan bəzi dəyişkənləri yeni saxladıq.
