Избришите Н-ти чвор са краја дате повезане листе


Ниво тешкоће Средњи
Често питани у адобе амазонка Арцесиум Фацтсет Интуит Зохо
Повезана листа

Изјава о проблему

Проблем „Избриши Н-ти чвор с краја дате повезане листе“ наводи да сте добили повезану листу са неким чворовима. А сада морате да уклоните н-ти чвор са краја повезане листе.

Пример

Избришите Н-ти чвор са краја дате повезане листе

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

Објашњење: Други чвор с краја је 2. па ћемо то избрисати. И након брисања чвора остаје нам повезана листа приказана у излазу.

Приступ

Повезана листа је линеарна структура података која користи предности показивача. А ово нам штеди велики рачунски напор током низа додавања додатних елемената. Сада је проблем уклонити н-ти чвор са повезане листе. Овде бих вам требао рећи да вам није обезбеђен број чворова на повезаној листи. Па који приступ треба изабрати да би се решио проблем? Када треба да избришемо н-ти чвор са краја повезане листе.

Наивни приступ

Наиван приступ биће прво израчунавање или израчунавање дужине повезане листе. Овај начин захтева да прво покренемо петљу до краја повезане листе. Али како ће израчунавање повезане листе помоћи у уклањању н-тог чвора с краја? Да бисмо решили проблем, прво ћемо израчунати дужину повезане листе. Тада ћемо дати унос одузети од дужине. Сад ћемо једноставно избришите чвор на дужини-н удаљености од главе.

Оптимизирани приступ

Оптимизирани приступ биће без израчунавања величине повезане листе. Постоји трик за решавање овог проблема. Прво прелазимо чвор који је иницијализован као глава све до нтог чвора од почетка. Сада стојимо на чвору који је на удаљености једнакој н од почетног чвора (главе). Затим иницијализујемо нову променљиву једнаку глави. Затим почните обилазити оба чвора све док први чвор не достигне последњи чвор повезане листе. Тада ће наша друга променљива бити на н + 1-том чвору од краја. Сада само треба да уклоните следећи чвор.

код

Ц ++ код за брисање Н-тог чвора са краја дате повезане листе

#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

Јава код за брисање Н-тог чвора са краја дате повезане листе

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

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

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

НА), јер смо прешли целу повезану листу која ће нас коштати линеарне временске сложености.

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

О (1), јер смо управо ускладиштили неке константне променљиве којима је потребна сложеност простора константна.