Изтрийте N-ти възел от края на дадения свързан списък


Ниво на трудност M
Често задавани в Кирпич Амазонка Арцезиум FactSet Intuit Zoho
Свързан списък

Декларация за проблема

Проблемът „Изтриване на N-ти възел от края на дадения свързан списък“ гласи, че сте получили свързан списък с някои възли. И сега трябва да премахнете n-ти възел от края на свързания списък.

Пример

Изтрийте N-ти възел от края на дадения свързан списък

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

Обяснение: Вторият възел от края е 2. така че ще го изтрием. И след изтриване на възела ни остава свързаният списък, показан в изхода.

Подход

Свързаният списък е линейна структура от данни, която се възползва от указателите. И това ни спестява големи изчислителни усилия за масив от добавяне на допълнителни елементи. Сега проблемът е да премахнете n-тия възел от свързания списък. Тук трябва да ви кажа, че не ви е предоставен броят на възлите в свързания списък. И така, какъв подход трябва да се избере, за да се реши проблемът? Когато трябва да изтрием n-тия възел от края на свързания списък.

Наивен подход

Наивен подход ще бъде първо да се изчисли или изчисли дължината на свързания списък. Този начин изисква от нас първо да стартираме цикъл до края на свързания списък. Но как изчисляването на свързания списък ще помогне при премахването на n-тия възел от края? За да разрешим проблема, първо ще изчислим дължината на свързания списък. След това ще извадим дадения вход от дължината. Сега просто ще го направим изтрийте възела на дължина-n разстояние от главата.

Оптимизиран подход

Оптимизиран подход ще бъде без изчисляване на размера на свързания списък. Има трик за решаване на този проблем. Първо, прекосяваме възел, който е инициализиран като глава до n-тия възел от началото. Сега стоим на възел, който е на разстояние, равно на n от началния възел (глава). След това инициализираме нова променлива, равна на head. След това започнете да обхождате и двата възела, докато първият възел достигне последния възел от свързания списък. По това време втората ни променлива ще бъде на n + 1-ия възел от края. Сега просто трябва да премахнете следващия възел.

код

C ++ код за изтриване на N-ти възел от края на дадения свързан списък

#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

Анализ на сложността

Сложност във времето

НА), защото сме преминали през целия свързан списък, което ще ни струва линейна сложност във времето.

Сложност на пространството

O (1), защото току-що сме съхранили някои константни променливи, изискваната сложност на пространството е постоянна.