ในบทช่วยสอนนี้ เราได้รับ linked list A ความยาว N และจำนวนเต็ม K เราต้องกลับลำดับคู่โหนดสลับกัน โดยขนาดของแต่ละคู่คือ K ยังกำหนดว่า N หาร K ลงตัว อาร์กิวเมนต์แรกคือหัวข้อ (head pointer) ของ linked list A และอาร์กิวเมนต์ที่สองคือจำนวนเต็ม K เช่น
ข้อมูลนำเข้า
5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2
ข้อมูลส่งออก
6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null
1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3
ข้อมูลส่งออก
5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null
แนวทางการหาคำตอบ
วิธี Iterative (วนซ้ำ)
- ท่อง 2K โหนดต่อการวนซ้ำ (หรือลูป) และบันทึกหัวและหางของแต่ละคู่ K โหนดในอินพุตที่กำหนด (Linked list) โดยใช้ join และ tail pointer
- จากนั้น กลับลำดับ K โหนดของ linked list และเชื่อมโหนดหางของรายการที่กลับแล้ว กับโหนดหัวของ linked list เริ่มต้น ที่ถูกชี้โดย join pointer
- จากนั้นเราจะเปลี่ยน current pointer ไปยัง K โหนดถัดไป
- หางของรายการปัจจุบันทำหน้าที่เป็นโหนดสุดท้าย (ซึ่งถูกชี้โดย new tail) และ join pointer จะชี้ไปหัวของรายการใหม่ (ที่กลับแล้ว) และพวกมันถูกรวมเข้าด้วยกัน เราจะวนซ้ำขั้นตอนเหล่านี้จนกว่าทุกโหนดจะทำตามขั้นตอนเดียวกัน
ตัวอย่างโค้ด (Iterative)
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* kAltReverse(struct Node* head, int k){ Node* prev = NULL; Node* curr = head; Node* temp = NULL; Node* tail = NULL; Node* newHead = NULL; Node* join = NULL; int t = 0; while (curr) { t = k; join = curr; prev = NULL; while (curr && t--) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } if (!newHead) newHead = prev; if (tail) tail->next = prev; tail = join; tail->next = curr; t = k; while (curr && t--) { prev = curr; curr = curr->next; } tail = prev; } return newHead; } void push(Node** head_ref, int new_data){ Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node){ int count = 0; while (node != NULL) { cout << node->data << " "; node = node->next; count++; } } int main(void){ Node* head = NULL; int i; for (i = 6; i <27; i+=3) push(&head, i); int k = 3; cout << "Given linked list \n"; printList(head); head = kAltReverse(head, k); cout << "\n Modified Linked list \n"; printList(head); return (0); }
ข้อมูลส่งออก
Given linked list 24 21 18 15 12 9 6 Modified Linked list 18 21 24 15 12 9 6
วิธี Recursive (เรียกซ้ำ)
- ท่อง K โหนดจากจุดเริ่มต้น และตั้งค่า temp เป็นโหนดที่ k+1
- กลับลำดับ K โหนดที่ท่องทั้งหมด
- ตั้งค่า next pointer ของโหนดสุดท้ายของคู่ K โหนดนั้นเป็น temp
- ข้ามการวนซ้ำครั้งถัดไป ซึ่งคู่ K โหนดเหล่านั้นต้องข้าม
- เรียกซ้ำตามขั้นตอนเหล่านี้สำหรับการกลับ K โหนดถัดไป จนถึงโหนดสุดท้าย
Pseudo Code
reverseAltK(head, k) curr = head prev = null next = null count = 0 WHILE count < k AND curr next = curr.next curr.next = prev prev = curr curr = next count = count + 1 IF head head.next = curr count = 0 WHILE count < k-1 AND curr curr = curr.next count = count + 1 IF curr curr.next = reverseKGroupAltRecursive(curr.next, k) return prev
ตัวอย่างโค้ด (Recursive)
#include <bits/stdc++.h> using namespace std; /* Link list node */ class node{ public: int data; node* next; }; /* Helper function for kAltReverse() */ node * _kAltReverse(node *node, int k, bool b); /* Alternatively reverses the given linked list in groups of given size k. */ node *kAltReverse(node *head, int k){ return _kAltReverse(head, k, true); } /* Helper function for kAltReverse(). It reverses k nodes of the list only if the third parameter b is passed as true, otherwise moves the pointer k nodes ahead and recursively calls iteself */ node * _kAltReverse(node *Node, int k, bool b){ if(Node == NULL) return NULL; int count = 1; node *prev = NULL; node *current = Node; node *next; /* The loop serves two purposes 1) If b is true, then it reverses the k nodes 2) If b is false, then it moves the current pointer */ while(current != NULL && count <= k){ next = current->next; /* Reverse the nodes only if b is true*/ if(b == true) current->next = prev; prev = current; current = next; count++; } /* 3) If b is true, then node is the kth node. So attach rest of the list after node. 4) After attaching, return the new head */ if(b == true){ Node->next = _kAltReverse(current, k, !b); return prev; } /* If b is not true, then attach rest of the list after prev. So attach rest of the list after prev */ else{ prev->next = _kAltReverse(current, k, !b); return Node; } } /* UTILITY FUNCTIONS */ /* Function to push a node */ void push(node** head_ref, int new_data){ /* allocate node */ node* new_node = new node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print linked list */ void printList(node *node){ int count = 0; while(node != NULL){ cout << node->data << " "; node = node->next; count++; } } // Driver Code int main(void){ /* Start with the empty list */ node* head = NULL; int i; // create a list 1->2->3->4->5...... ->20 for(i = 20; i > 0; i--) push(&head, i); cout << "Given linked list \n"; printList(head); head = kAltReverse(head, 3); cout << "\nModified Linked list \n"; printList(head); return(0); }
ข้อมูลส่งออก
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
สรุป
บทช่วยสอนนี้สอนวิธีกลับโหนด K ตัวสลับกันใน Singly Linked List และ pseudo-code การนำไปใช้ใน C++ สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ ในแนวทางนี้ เราใช้การเรียกซ้ำเพื่อกลับ K โหนดสลับกันและข้ามโหนดที่เหลือ หวังว่าบทช่วยสอนนี้จะมีประโยชน์
