หาโหนดที่ k จากกลางไปหาหัวของ Linked List ใน C++

โจทย์

ได้รับ Linked List และจำนวน k ทางเราต้อง หาโหนดที่ k จากโหนดกลาง (Middle) ไปทางหัว (Head)

ตัวอย่าง

Input: 4→2→7→1→9→12→8→10→5, k = 2

Output: 7

อธิบาย: โหนดกลางคือ 9, โหนดที่ 2 จากกลางไปหัวคือ 7

แนวทางแก้ปัญหา

1. นับจำนวนโหนดทั้งหมด n
2. โหนดกลางอยู่ตำแหน่ง n/2 + 1 (1-indexed)
3. โหนดที่ k จากกลางไปหัวอยู่ตำแหน่ง (n/2 + 1) - k จากหัว

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

struct Node { int data; struct Node* next; };

void pushNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int findKmiddleNode(struct Node* head_ref, int k) {
    int n = 0;
    struct Node* counter = head_ref;
    while (counter != NULL) { n++; counter = counter->next; }
    int reqNode = ((n / 2 + 1) - k);
    if (reqNode <= 0) return -1;
    struct Node* current = head_ref;
    int count = 1;
    while (current != NULL) {
        if (count == reqNode) return current->data;
        count++; current = current->next;
    }
    return -1;
}

int main() {
    struct Node* head = NULL;
    int k = 2;
    pushNode(&head, 5); pushNode(&head, 10); pushNode(&head, 8);
    pushNode(&head, 12); pushNode(&head, 9); pushNode(&head, 1);
    pushNode(&head, 7); pushNode(&head, 2); pushNode(&head, 4);
    cout << k << "th element from beginning towards head is " << findKmiddleNode(head, k);
    return 0;
}

ผลลัพธ์

2th element from beginning towards head is 7