Выдаліць вузел са звязанага спісу без указальніка галоўкі


Узровень складанасці Лёгка
Часта пытаюцца ў GE Healthcare MAQ
Звязаны спіс Тэхнічны сцэнар

Пастаноўка праблемы

Праблема «Выдаліць вузел са звязанага спісу без указальніка галоўкі» абвяшчае, што ў вас ёсць звязаны спіс з некаторымі вузламі. Цяпер вы хочаце выдаліць вузел, але ў вас няма адраса бацькоўскага вузла. Так што выдаліце ​​гэты вузел.

Прыклад

Выдаліць вузел са звязанага спісу без указальніка галоўкі

2->3->4->5->6->7
Node to be deleted: 4
2->3->5->6->7

Тлумачэнне: Паколькі мы хацелі выдаліць вузел са значэннем 4. Мы выдалілі яго са звязанага спіса і пакінулі спіс, які згадваецца ў выходных дадзеных.

Падыход да выдалення вузла без указальніка галавы

Звязаны спіс - гэта лінейная структура дадзеных, якая мае велізарную перавагу перад масівам у тым, што яна можа адрознівацца па памеры. Калі вы хочаце дадаць элемент у звязаны спіс, вы можаце дадаць яго за O (1) раз. Улічваючы, што вы ўстаўляеце элемент у першую чаргу. Але калі вам трэба было зрабіць тое ж самае ў звычайным масіве. Для гэтага вам абыдзецца O (N) часу. Такім чынам, выгадна выкарыстоўваць звязаны спіс па масіве ў рэальных прыкладаннях. І звязаны спіс дасягае ўсяго гэтага, таму што не захоўвае дадзеныя як сумежны кавалак. Ён захоўвае кожны элемент у нейкім выпадковым месцы. Але як тады падтрымліваць парадак? Адказ на гэтае пытанне заключаецца ў тым, што звязаны спіс выкарыстоўвае паказальнік. Кожны вузел паказвае на іншы вузел у звязаным спісе, і такім чынам нам не трэба выдзяляць адзін кавалак змены, які, у сваю чаргу, запатрабаваў бы шмат вылічэнняў.

Калі быў дадзены паказальнік галавы

Цяпер праблема просіць нас выдаліць вузел. Як правіла, нам даецца адрас вузла і мы павінны выдаліць наступны вузел у звязаным спісе. Але тут мы павінны выдаліць вузел, адрас якога нам дадзены. Адзін са спосабаў вырашыць гэтую праблему - спачатку перайсці ўвесь звязаны спіс. Затым захавайце бацькоўскі ўчастак кожнага вузла і перапыніце цыкл, калі вы знаходзіцеся ў вузле, які прадастаўляецца ў якасці ўваходных дадзеных. Такім чынам, у выніку мы маем бацькоўскі вузел, які трэба выдаліць. Такім чынам, цяпер праблема зменена на простае выдаленне вузла ў звязаным спісе, чый бацькоўскі адрас дадзены. Але гэта будзе каштаваць нам O (N) аперацый. Але гэты спосаб можна выкарыстоўваць толькі тады, калі ў вас ёсць паказальнік галавы.

Рашэнне

Падыход да праблемы "Выдаленне вузла са звязанага спісу без указальніка галоўкі" заключаецца ў абмене дадзенымі вузла, які трэба выдаліць, і наступнага вузла ў звязаным спісе. Кожны вузел у звязаным спісе захоўвае наступны вузел. Такім чынам, гэтая аперацыя мае толькі O (1) часовую складанасць. Цяпер, калі дадзеныя былі заменены. У чарговы раз мы змянілі праблему на выдаленне вузла, бацькоўскі адрас якога ўказаны. Такім чынам, цяпер нам лягчэй вырашыць праблему. Але ёсць адзін краявы выпадак, калі нам трэба выдаліць канчатковы вузел, але мы не зможам яго выдаліць. Таму што наступнага вузла няма.

код

Код C ++ для выдалення вузла без указальніка на галаву

#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;
}

void deletedNode(node* &head, node* toBeDeleted){
  if(toBeDeleted == NULL)
    return;
  else{
    if(toBeDeleted->next == NULL){
      cout<<"Last node can't be freed";
    }
    // store or swap but ( the data of current node will be deleted)
    toBeDeleted->data = toBeDeleted->next->data;
    toBeDeleted->next = toBeDeleted->next->next;
  }
}

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;
  }
  deletedNode(head, toBeDeleted);

  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 5 6 7

Код Java для выдалення вузла без указальніка галавы

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 deletedNode(node head, node toBeDeleted){
    if(toBeDeleted == null)
      return null;
    else{
      if(toBeDeleted.next == null){
        System.out.print("Last node can't be freed");
        return null;
      }
      // store or swap but ( the data of current node will be deleted)
      toBeDeleted.data = toBeDeleted.next.data;
      toBeDeleted.next = toBeDeleted.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);
    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);
 
    System.out.print("Old Linked List: ");
    node tmp = head;
    while(tmp != null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
    head = deletedNode(head, toBeDeleted);
 
    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 5 6 7

Аналіз складанасці

Складанасць часу

O (1), таму што замена можа быць недаступная ў пастаянны час. А потым мы проста мяняем некаторыя паказальнікі, што зноў з'яўляецца пастаяннай аперацыяй па часе.

Касмічная складанасць

O (1), таму што выкарыстаныя намі зменныя не залежаць ад колькасці вузлоў у звязаным спісе. Такім чынам, складанасць касмічнай прасторы таксама сталая.