ลบทุกโหนด K-th ของรายการที่เชื่อมโยง

ในบทความนี้ เราจะอธิบายวิธีการลบทุกโหนดที่ k ของรายการที่เชื่อมโยง เราต้องลบทุกโหนดที่อยู่บนตัวคูณของ k นั่นคือเราต้องลบโหนดที่ตำแหน่ง k, 2*k, 3*k เป็นต้น

Input : 112->231->31->41->54->63->71->85
   k = 3
Output : 112->231->41->54->71->85
Explanation: As 3 is the k-th node after its deletion list would be :
First iteration :112->231->41->54->63->71->85
Now we count from 41 the next kth node is 63
After the second iteration our list will become : 112->231->41->54->71->85
And our iteration continues like this.

Input: 14->21->23->54->56->61
   k = 1
Output: Empty list
Explanation: All nodes need to be deleted

ในปัญหานี้ เราจะใช้แนวทางปกติที่มีประสิทธิภาพเพียงพอเพื่อที่เราจะได้ไม่ต้องปรับให้เหมาะสม

แนวทางในการหาทางออก

ในปัญหานี้ เราจะสำรวจรายการเชื่อมโยงด้วยตัวนับ หากตัวนับถึง k เราจะลบโหนดนั้นและรีเฟรชตัวนับเพื่อค้นหาองค์ประกอบถัดไปในตำแหน่งที่ k จากโหนดปัจจุบัน

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list

   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function

   if(prev == NULL) {
      prev = curr;
      curr = curr -> next;
      free(prev);
      prev = NULL;
   } else {
      prev -> next = curr -> next;
      auto tmp = curr;
      free(tmp); // freeing the space
   }
}
/* Function to print linked list */
void displayList(struct Node *head) {
   struct Node *temp = head;
   while (temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
}
// Function to create a new node.
struct Node *newNode(int x) {
   Node *temp = new Node;
   temp->data = x;
   temp->next = NULL;
   return temp;
}
int main() {
   struct Node* head = NULL;
   push(&head, 80);
   push(&head, 70);
   push(&head, 60);
   push(&head, 50);
   push(&head, 40);
   push(&head, 30);
   push(&head, 20);
   int k = 3; // given k
   Node* curr = head; // current pointer
   Node* prev = NULL; // previous pointer
   int count = 1; // position counter
   if(head == NULL || k == 0) // if list is already empty or k = 0
      cout << "Invalid\n";
   else {
      while(curr) { // traversing the list
         if(count == k) {
            deletek(prev, curr);
            curr = prev -> next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr -> next;
         }
      }
      displayList(head); // printing the new list
   }
   return 0;
}

ผลลัพธ์

20 30 50 60 80

วิธีการข้างต้นมีความซับซ้อนของเวลา O(N) โดยที่ N คือขนาดของรายการเชื่อมโยงที่เรากำหนด

คำอธิบายของโค้ดด้านบน

ในแนวทางข้างต้น เราเก็บสามสิ่งไว้ในมือก่อน ตัวชี้ปัจจุบัน ตัวชี้ที่สองตัวก่อนหน้า และตัวนับตำแหน่งที่สาม ตอนนี้เราลบบางโหนดเมื่อตัวนับตำแหน่งของเราเท่ากับรู้ว่าเราเรียกใช้ฟังก์ชันเพื่อลบด้วยตัวนับก่อนหน้าและปัจจุบันเนื่องจากพารามิเตอร์ ตอนนี้เราลบโหนดปัจจุบันและเพิ่มพื้นที่ว่างทันทีเมื่อฟังก์ชันลบเสร็จสิ้น ตอนนี้เราเปลี่ยนตัวชี้ปัจจุบันเป็น องค์ประกอบถัดไปและรีเฟรชตัวนับของเราเป็น 1 และวนซ้ำบล็อกนี้จนกว่าปัจจุบันของเราจะกลายเป็น NULL

บทสรุป

ในบทความนี้ เราแก้ปัญหาในการลบโหนดที่ k ของรายการที่เชื่อมโยงทั้งหมด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์