מחק את הצומת Nth מסוף הרשימה המקושרת הנתונה


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית ארצסיום סט עובדות אינטואיט Zoho
רשימה מקושרת

הצהרת בעיה

הבעיה "מחק צומת Nth מסוף הרשימה המקושרת הנתונה" קובעת שקיבלת רשימה מקושרת עם כמה צמתים. ועכשיו עליך להסיר את הצומת ה- nt מסוף הרשימה המקושרת.

דוגמה

מחק את הצומת Nth מסוף הרשימה המקושרת הנתונה

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

הסבר: הצומת השני מהסוף הוא 2. אז נמחק את זה. ולאחר מחיקת הצומת נותרה לנו הרשימה המקושרת המוצגת בפלט.

גישה

רשימה מקושרת היא מבנה נתונים ליניארי המנצל את המצביעים. וזה חוסך לנו מאמץ חישובי גדול על פני מערך של הוספת אלמנטים נוספים. כעת הבעיה היא להסיר את הצומת nth מהרשימה המקושרת. כאן אני אמור לך שלא מספקים לך את מספר הצמתים ברשימה המקושרת. אז באיזו גישה צריך לבחור כדי לפתור את הבעיה? כאשר עלינו למחוק את הצומת ה- n מסוף הרשימה המקושרת.

גישה נאיבית

גישה נאיבית תהיה תחילה לחשב או לחשב את אורך הרשימה המקושרת. דרך זו מחייבת אותנו להפעיל לולאה תחילה עד סוף הרשימה המקושרת. אך כיצד חישוב הרשימה המקושרת יסייע בהסרת צומת nth מהסוף? כדי לפתור את הבעיה נחשב תחילה את אורך הרשימה המקושרת. ואז נפחית את הקלט הנתון מהאורך. עכשיו פשוט נעשה מחק את הצומת במרחק n- מהראש.

גישה אופטימלית

גישה מותאמת תהיה ללא חישוב גודל הרשימה המקושרת. יש טריק לפתור בעיה זו. ראשית, אנו חוצים צומת אשר מאותחל כראש עד לצומת ה- 1 מההתחלה. כעת אנו עומדים בצומת שנמצא במרחק השווה ל- n מצומת ההתחלה (ראש). לאחר מכן אנו מאותחלים משתנה חדש השווה לראש. ואז התחל לחצות את שני הצמתים עד שהצומת הראשון יגיע לצומת האחרון של הרשימה המקושרת. באותה עת המשתנה השני שלנו יהיה בצומת n + XNUMX מהסוף. עכשיו אתה רק צריך להסיר את הצומת הבא.

קופונים

קוד 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

קוד Java כדי למחוק את הצומת 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 (N) מכיוון שעברנו את כל הרשימה המקושרת שתעלה לנו מורכבות זמן ליניארית.

מורכבות בחלל

O (1), מכיוון שרק אחסנו כמה משתנים קבועים מורכבות החלל הנדרשת קבועה.