ລົບ Node ຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍບໍ່ມີຕົວຊີ້  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ GE Healthcare MAQ
ບັນຊີທີ່ເຊື່ອມໂຍງ ເຕັກນິກ Scripter

ຖະແຫຼງການບັນຫາ  

ບັນຫາ "ລຶບ Node ຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍບໍ່ມີຕົວຊີ້ຫົວ" ລະບຸວ່າທ່ານມີລາຍຊື່ທີ່ເຊື່ອມໂຍງກັບບາງຂໍ້. ດຽວນີ້ທ່ານຕ້ອງການລຶບ node ແຕ່ທ່ານບໍ່ມີທີ່ຢູ່ຂອງມັນ. ສະນັ້ນລົບລ້າງ node ນີ້.

ຍົກຕົວຢ່າງ  

ລົບ Node ຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍບໍ່ມີຕົວຊີ້Pin

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

ຄໍາອະທິບາຍ: ນັບຕັ້ງແຕ່ພວກເຮົາຕ້ອງການລຶບ node ດ້ວຍຄ່າ 4. ພວກເຮົາເອົາມັນອອກຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະຍັງເຫຼືອຢູ່ກັບລາຍຊື່ທີ່ຖືກກ່າວເຖິງໃນຜົນຜະລິດ.

ວິທີການທີ່ຈະລຶບ node ໂດຍບໍ່ມີຕົວຊີ້  

ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງແມ່ນໂຄງສ້າງຂໍ້ມູນເສັ້ນທີ່ມີປະໂຫຍດອັນໃຫຍ່ຫຼວງ ເໜືອ ອາເລແມ່ນວ່າມັນສາມາດແຕກຕ່າງກັນໃນຂະ ໜາດ. ຖ້າທ່ານຕ້ອງການເພີ່ມອົງປະກອບໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ, ທ່ານສາມາດເພີ່ມມັນໄດ້ໃນເວລາ O (1). ພິຈາລະນາວ່າທ່ານ ກຳ ລັງໃສ່ອົງປະກອບເຂົ້າໃນອັນດັບ ທຳ ອິດ. ແຕ່ຖ້າທ່ານຕ້ອງເຮັດແບບດຽວກັນໃນຂບວນປົກກະຕິ. ມັນຈະເຮັດໃຫ້ທ່ານເສຍຄ່າເວລາ (N) ເພື່ອເຮັດແນວນັ້ນ. ດັ່ງນັ້ນມັນຈຶ່ງເປັນການດີທີ່ຈະ ນຳ ໃຊ້ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງຜ່ານບັນດາເອກະສານສະ ໝັກ ຕົວຈິງ. ແລະບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງກໍ່ບັນລຸໄດ້ທັງ ໝົດ ເພາະມັນບໍ່ໄດ້ເກັບຂໍ້ມູນເປັນທ່ອນຕິດຕໍ່ກັນ. ມັນເກັບຮັກສາແຕ່ລະອົງປະກອບໃນບາງສະຖານທີ່ແບບສຸ່ມ. ແຕ່ແລ້ວມັນຮັກສາຄວາມເປັນລະບຽບຮຽບຮ້ອຍແນວໃດ? ຄຳ ຕອບ ສຳ ລັບ ຄຳ ຖາມນີ້ແມ່ນ, ລາຍຊື່ທີ່ເຊື່ອມໂຍງຈະໃຊ້ຕົວຊີ້. ແຕ່ລະ node ຊີ້ໃຫ້ເຫັນ node ອື່ນໃນບັນຊີທີ່ມີການເຊື່ອມໂຍງແລະດ້ວຍວິທີນີ້ພວກເຮົາບໍ່ ຈຳ ເປັນຕ້ອງຈັດສັນການປ່ຽນແປງເປັນທ່ອນດຽວເຊິ່ງຈະຕ້ອງມີການ ຄຳ ນວນຫຼາຍ.

ເບິ່ງ
ບັນຊີລາຍຊື່ການເຊື່ອມໂຍງ K Sorted

ຖ້າຕົວຊີ້ຫົວໄດ້ຮັບ

ດຽວນີ້ປັນຫາຖາມພວກເຮົາ ລົບຂໍ້. ໂດຍທົ່ວໄປ, ພວກເຮົາໄດ້ຮັບທີ່ຢູ່ຂອງ node ແລະຖືກ ກຳ ນົດໃຫ້ລຶບ node ຕໍ່ໄປໃນລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ແຕ່ໃນທີ່ນີ້ພວກເຮົາ ຈຳ ເປັນຕ້ອງລຶບ node ທີ່ມີທີ່ຢູ່ໃຫ້ພວກເຮົາ. ວິທີ ໜຶ່ງ ໃນການແກ້ໄຂບັນຫານີ້ແມ່ນການ ທຳ ອິດບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງ ໝົດ. ຫຼັງຈາກນັ້ນ, ເກັບຮັກສາພໍ່ແມ່ຂອງແຕ່ລະ node ແລະແຍກວົງຈອນໃນເວລາທີ່ທ່ານຢູ່ໃນ node ທີ່ຖືກສະຫນອງໃຫ້ເປັນວັດສະດຸປ້ອນ. ວິທີນີ້ໃນທີ່ສຸດພວກເຮົາມີພໍ່ແມ່ຂອງຂໍ້ທີ່ຈະຖືກລຶບອອກ. ດັ່ງນັ້ນຕອນນີ້ບັນຫາຈະຖືກປ່ຽນໄປເປັນການລຶບງ່າຍໆຂອງ node ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງເຊິ່ງພໍ່ແມ່ໄດ້ຮັບທີ່ຢູ່. ແຕ່ການເຮັດສິ່ງນີ້ຈະເຮັດໃຫ້ພວກເຮົາປະຕິບັດການຈ່າຍເງິນ O (N). ແຕ່ວິທີນີ້ສາມາດໃຊ້ໄດ້ພຽງແຕ່ໃນເວລາທີ່ທ່ານມີຕົວຊີ້ຫົວ.

ການແກ້ໄຂ

ວິທີການ ສຳ ລັບບັນຫາ“ ລົບ Node ຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍບໍ່ມີຕົວຊີ້ຫົວ” ຈະເປັນການປ່ຽນຂໍ້ມູນຂອງຂໍ້ທີ່ຈະຖືກລຶບອອກແລະຂໍ້ຕໍ່ຢູ່ໃນລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ແຕ່ລະ node ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງເກັບຮັກສາເຊິ່ງ node ຢູ່ຕໍ່ໄປ. ດັ່ງນັ້ນການປະຕິບັດງານນີ້ມີພຽງແຕ່ O (1) ເວລາທີ່ສັບສົນ. ດຽວນີ້ເມື່ອຂໍ້ມູນໄດ້ຖືກແລກປ່ຽນແລ້ວ. ອີກຄັ້ງ ໜຶ່ງ, ພວກເຮົາໄດ້ປ່ຽນບັນຫາດັ່ງກ່າວໄປເປັນການລຶບຂໍ້ທີ່ມີທີ່ຢູ່ຂອງພໍ່ແມ່. ສະນັ້ນດຽວນີ້ມັນງ່າຍກວ່າ ສຳ ລັບພວກເຮົາທີ່ຈະແກ້ໄຂບັນຫາ. ແຕ່ມີກໍລະນີທີ່ມີຂອບ ໜຶ່ງ ໃນເວລາທີ່ພວກເຮົາຕ້ອງລົບລ້າງຂໍ້ສຸດທ້າຍແຕ່ພວກເຮົາຈະບໍ່ສາມາດລຶບສິ່ງນັ້ນໄດ້. ເນື່ອງຈາກວ່າບໍ່ມີ node ຕໍ່ໄປ.

ເບິ່ງ
ເງິນເດືອນສະເລ່ຍບໍ່ລວມວິທີແກ້ໄຂບັນຫາເງິນເດືອນຂັ້ນຕໍ່າແລະສູງສຸດ

ລະຫັດ  

ລະຫັດ C ++ ເພື່ອລຶບ node ໂດຍບໍ່ມີຕົວຊີ້

#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 ເພື່ອລຶບ node ໂດຍບໍ່ມີຕົວຊີ້

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

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

ໂອ (1), ເພາະວ່າການແລກປ່ຽນສາມາດຫຼຸດລົງໃນເວລາຄົງທີ່. ແລະຫຼັງຈາກນັ້ນພວກເຮົາພຽງແຕ່ປ່ຽນຈຸດບາງອັນເຊິ່ງເປັນການ ດຳ ເນີນງານທີ່ໃຊ້ເວລາຄົງທີ່ອີກເທື່ອ ໜຶ່ງ.

ເບິ່ງ
ປ່ຽນຄືນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ເນື່ອງຈາກວ່າຕົວແປທີ່ພວກເຮົາໄດ້ໃຊ້ບໍ່ຂື້ນກັບ ຈຳ ນວນຂໍ້ໃນບັນຊີທີ່ເຊື່ອມໂຍງ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຍັງຄົງທີ່.