លុបថ្នាំងទីពីចុងនៃបញ្ជីដែលបានភ្ជាប់


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon អាសេស្យូម រោងចក្រ វិចារណញាណ Zoho
បញ្ជីភ្ជាប់

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ លុបថ្នាំងទីពីចុងនៃបញ្ជីភ្ជាប់ដែលបានផ្តល់ឱ្យ” ចែងថាអ្នកត្រូវបានផ្តល់បញ្ជីភ្ជាប់ជាមួយថ្នាំងមួយចំនួន។ ហើយឥឡូវអ្នកត្រូវដកថ្នាំងទី ១ ចេញពីចុងបញ្ជីដែលភ្ជាប់។

ឧទាហរណ៍

លុបថ្នាំងទីពីចុងនៃបញ្ជីដែលបានភ្ជាប់

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

ការពន្យល់ៈថ្នាំងទី ២ ពីចុងបញ្ចប់គឺ ៦ ។ ដូច្នេះយើងនឹងលុបវាចោល។ ហើយបន្ទាប់ពីលុបថ្នាំងយើងនៅសល់ជាមួយបញ្ជីភ្ជាប់ដែលបង្ហាញក្នុងលទ្ធផល។

វិធីសាស្រ្ត

បញ្ជីភ្ជាប់គឺជារចនាសម្ព័ន្ធទិន្នន័យលីនេអ៊ែរដែលទាញយកអត្ថប្រយោជន៍ពីអ្នកចង្អុល។ ហើយនេះជួយសន្សំសំចៃការខិតខំគណនាដ៏អស្ចារ្យរបស់យើងលើអារេនៃការបន្ថែមធាតុបន្ថែម។ ឥឡូវនេះបញ្ហាគឺត្រូវយកថ្នាំងចេញពីបញ្ជីដែលបានភ្ជាប់។ នៅទីនេះខ្ញុំគួរតែប្រាប់អ្នកថាអ្នកមិនត្រូវបានផ្តល់ឱ្យនូវចំនួនថ្នាំងនៅក្នុងបញ្ជីដែលបានភ្ជាប់ទេ។ ដូច្នេះវិធីសាស្រ្តអ្វីដែលមនុស្សម្នាក់គួរតែជ្រើសរើសដើម្បីដោះស្រាយបញ្ហា? នៅពេលដែលយើងត្រូវការលុបថ្នាំងទីពីចុងនៃបញ្ជីភ្ជាប់។

វិធីសាស្ត្រណាតូស

វិធីឆោតល្ងង់នឹងត្រូវគណនាដំបូងឬគណនាប្រវែងនៃបញ្ជីដែលបានភ្ជាប់។ វិធីនេះតម្រូវឱ្យយើងដំណើរការរង្វិលជុំដំបូងរហូតដល់ចុងបញ្ចប់នៃបញ្ជីភ្ជាប់។ ប៉ុន្តែតើការគណនានៃបញ្ជីដែលបានភ្ជាប់នឹងជួយក្នុងការដកចេញថ្នាំង nH ពីទីបញ្ចប់យ៉ាងដូចម្តេច? ដើម្បីដោះស្រាយបញ្ហាដំបូងយើងនឹងគណនារយៈពេលនៃបញ្ជីភ្ជាប់។ បន្ទាប់មកយើងនឹងដកធាតុបញ្ចូលដែលបានផ្តល់ឱ្យពីប្រវែង។ ឥឡូវនេះយើងនឹងនិយាយដោយសាមញ្ញ លុបថ្នាំង នៅចម្ងាយ-n ចម្ងាយពីក្បាល។

វិធីសាស្រ្តប្រសើរបំផុត

វិធីសាស្រ្តធ្វើឱ្យប្រសើរនឹងត្រូវបានដោយមិនចាំបាច់គណនាទំហំនៃបញ្ជីដែលបានភ្ជាប់។ មានល្បិចដោះស្រាយបញ្ហានេះ។ ដំបូងយើងឆ្លងកាត់ថ្នាំងដែលត្រូវបានចាប់ផ្តើមជាក្បាលរហូតដល់ថ្នាំងទី n ពីដំបូង។ ឥឡូវនេះយើងកំពុងឈរនៅថ្នាំងដែលមានចម្ងាយស្មើនឹង n ពីថ្នាំងចាប់ផ្តើម (ក្បាល) ។ បន្ទាប់មកយើងចាប់ផ្តើមអថេរថ្មីស្មើនឹងក្បាល។ បន្ទាប់មកចាប់ផ្តើមឆ្លងកាត់ថ្នាំងទាំងពីររហូតដល់ថ្នាំងទីមួយឈានដល់ថ្នាំងចុងក្រោយនៃបញ្ជីដែលបានភ្ជាប់។ នៅពេលនោះអថេរទីពីររបស់យើងនឹងស្ថិតនៅ n + 1 node ពីចុងបញ្ចប់។ ឥឡូវអ្នកគ្រាន់តែត្រូវការដោះចេញថ្នាំងបន្ទាប់។

លេខកូដ

លេខកូដ 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;
}

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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ពីព្រោះយើងបានឆ្លងកាត់បញ្ជីដែលបានភ្ជាប់ទាំងមូលដែលនឹងធ្វើឱ្យយើងស្មុគស្មាញពេលវេលាលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ពីព្រោះយើងទើបតែទុកអថេរថេរមួយចំនួនភាពស្មុគស្មាញនៃទំហំដែលត្រូវការគឺថេរ។