ในบทความนี้ เราจะอธิบายวิธีการลบโหนดทุก k-th ของ Linked List เราต้องลบโหนดที่อยู่ในตำแหน่งที่เป็นพหุคูณของ k เช่น k, 2k, 3k, ฯลฯ
Input : 112→231→31→41→54→63→71→85, k = 3 Output : 112→231→41→54→71→85 Explanation: โหนดที่ 3 คือ k-th node หลังลบลิสต์จะเป็น: รอบแรก: 112→231→41→54→63→71→85 นับจาก 41 โหนด k-th ถัดไปคือ 63 รอบที่สอง: 112→231→41→54→71→85 ทำต่อไปเช่นนี้ Input: 14→21→23→54→56→61, k = 1 Output: Empty list Explanation: ลบทุกโหนด
ในปัญหานี้ เราจะใช้วิธีปกติที่มีประสิทธิภาพพอ ไม่ต้อง optimize เพิ่ม
แนวทางแก้ปัญหา
ในปัญหานี้ เราจะเดินผ่าน Linked List พร้อมตัวนับ (counter) หากตัวนับถึง k เราจะลบโหนดนั้นและรีเซ็ตตัวนับเพื่อหาตัวถัดไปในตำแหน่ง k-th จากโหนดปัจจุบัน
ตัวอย่างโค้ด
#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) {
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
void deletek(Node* prev, Node* curr) {
// ฟังก์ชันลบ
if (prev == NULL) {
prev = curr;
curr = curr->next;
free(prev);
prev = NULL;
} else {
prev->next = curr->next;
auto tmp = curr;
free(tmp); // ปล่อยหน่วยความจำ
}
}
/* ฟังก์ชันพิมพ์ linked list */
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
// ฟังก์ชันสร้างโหนดใหม่
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; // k ที่กำหนด
Node* curr = head; // current pointer
Node* prev = NULL; // previous pointer
int count = 1; // ตัวนับตำแหน่ง
if (head == NULL || k == 0) // ถ้าลิสต์ว่างหรือ k=0
cout << "Invalid\n";
else {
while (curr) { // เดินผ่านลิสต์
if (count == k) {
deletek(prev, curr);
curr = prev ? prev->next : head;
count = 1;
} else {
count++;
prev = curr;
curr = curr->next;
}
}
displayList(head); // พิมพ์ลิสต์ใหม่
}
return 0;
}
ผลลัพธ์
20 30 50 60 80
วิธีนี้มี Time Complexity O(N) โดย N คือขนาดของ Linked List
คำอธิบายโค้ด
เราเก็บ 3 อย่าง: current pointer, previous pointer, และ position counter ตอนที่ counter เท่ากับ k เราเรียกฟังก์ชันลบพร้อมส่ง previous และ current หลังลบเสร็จ เราเลื่อน current ไปตัวถัดไป รีเซ็ต counter เป็น 1 และวนลูปต่อจน current เป็น NULL
สรุป
ในบทความนี้ เราแก้ปัญหาการลบโหนดทุก k-th ของ Linked List เรียนรู้โปรแกรม C++ และแนวทางการแก้ปัญหา สามารถเขียนในภาษาอื่นได้เช่น C, Java, Python หวังว่าจะเป็นประโยชน์
