گره Nth را از انتهای لیست پیوند داده شده حذف کنید


سطح دشواری متوسط
اغلب در خشت آمازون ارسیسیوم واقعیت تعلیم دادن ZOHO
لینک شده

بیان مسأله

مسئله "حذف گره Nth از انتهای لیست پیوند داده شده" بیان می کند که یک لیست پیوندی با برخی از گره ها به شما داده می شود. اکنون باید nth گره را از انتهای لیست پیوند داده شده حذف کنید.

مثال

گره Nth را از انتهای لیست پیوند داده شده حذف کنید

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

توضیح: گره دوم از انتها 2 است. بنابراین ما آن را حذف خواهیم کرد. و پس از حذف گره ، ما با لیست پیوندی که در خروجی نشان داده شده است ، می مانیم.

روش

Linked List یک ساختار داده ای خطی است که از مزایای اشاره گرها بهره می برد. و این باعث می شود که ما در محاسبه یک سری افزودن عناصر اضافی ، محاسبات زیادی انجام دهیم. اکنون مشکل حذف node گره از لیست پیوند داده شده است. در اینجا باید به شما بگویم که تعداد گره های موجود در لیست پیوندی به شما ارائه نمی شود. بنابراین برای حل مسئله چه رویکردی باید انتخاب شود؟ هنگامی که ما نیاز به حذف گره n از انتهای لیست پیوند داده شده داریم.

رویکرد ساده لوحانه

یک رویکرد ساده لوحانه ابتدا محاسبه یا محاسبه طول لیست پیوند یافته است. این روش ما را ملزم می کند که ابتدا یک حلقه را تا انتهای لیست پیوندی اجرا کنیم. اما محاسبه لیست پیوندی چگونه به حذف گره n از انتها کمک می کند؟ برای حل این مشکل ابتدا طول لیست پیوند داده شده را محاسبه خواهیم کرد. سپس ورودی داده شده را از طول کم می کنیم. در حال حاضر ما به سادگی گره را حذف کنید در طول n فاصله از سر.

رویکرد بهینه شده

یک رویکرد بهینه بدون محاسبه اندازه لیست پیوندی خواهد بود. یک ترفند برای حل این مشکل وجود دارد. ابتدا گره ای را رد می کنیم که از ابتدا به عنوان سر تا گره n ام آغاز شده است. اکنون ما در یک گره ایستاده ایم که در فاصله برابر n از گره شروع (سر) قرار دارد. سپس یک متغیر جدید برابر با مقدار اولیه را مقدار دهی می کنیم. سپس شروع به پیمایش هر دو گره کنید تا اولین گره به آخرین گره از لیست پیوسته برسد. در آن زمان متغیر دوم ما از انتها در گره n + 1 قرار می گیرد. اکنون فقط باید گره بعدی را حذف کنید.

رمز

کد ++ C برای حذف گره Nth از انتهای لیست پیوند داده شده

#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

تحلیل پیچیدگی

پیچیدگی زمان

بر)، زیرا ما از کل لیست پیوندی عبور کرده ایم که هزینه پیچیدگی زمانی خطی برای ما خواهد داشت.

پیچیدگی فضا

O (1) ، زیرا ما فقط برخی از متغیرهای ثابت را ذخیره کرده ایم ، پیچیدگی فضای مورد نیاز ثابت است.