Verilən əlaqəli siyahının sonundan Nth nodu silin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Arcezium Məlumat dəsti Intuit Zoho
Bağlı siyahıBaxılıb 30

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

Verilən əlaqəli siyahının sonundan Nth nodu silinPin

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.

Translate »