เขียนฟังก์ชันหาโหนดที่ N ใน Linked List (C++)

โจทย์

ได้รับ Linked List และ index n ต้องเขียนฟังก์ชันเพื่อหาโหนดที่ n (0-indexed หรือ 1-indexed ตามกำหนด)

ตัวอย่าง

Input: linked list = 34 → 4 → 9 → 1, n = 2
Output: 9 (โหนด index 2 คือ 9)

วิธีแก้ปัญหา

เดินทาง (traverse) linked list จาก head ไปทีละโหนด นับ index จนถึงตำแหน่งที่ต้องการ

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void insertNode(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;
}

int findNodeAt(Node* head, int index) {
    Node* current = head;
    int count = 0;
    
    while (current != nullptr) {
        if (count == index) {
            return current->data;
        }
        count++;
        current = current->next;
    }
    
    // หาก index เกินขนาด list
    return -1;  // หรือ throw exception
}

int main() {
    Node* head = nullptr;
    insertNode(&head, 8);
    insertNode(&head, 2);
    insertNode(&head, 9);
    insertNode(&head, 1);
    insertNode(&head, 4);
    // List: 4 → 1 → 9 → 2 → 8
    
    int n = 2;
    cout << "Element at index " << n << " is " << findNodeAt(head, n);
    return 0;
}

ผลลัพธ์

Element at index 2 is 9

การปรับปรุงและข้อควรระวัง

1. Bounds Checking

int findNodeAtSafe(Node* head, int index) {
    if (index < 0) return -1;  // หรือ throw
    
    Node* current = head;
    int count = 0;
    while (current != nullptr && count < index) {
        current = current->next;
        count++;
    }
    
    if (current == nullptr) return -1;  // Index out of bounds
    return current->data;
}

2. ใช้ Two Pointers สำหรับ "Nth from end"

หากโจทย์เป็น "หาโหนดที่ N จากท้าย" ใช้ two pointers:

int findNthFromEnd(Node* head, int n) {
    Node *fast = head, *slow = head;
    
    // เคลื่อน fast ไป n ก้าวก่อน
    for (int i = 0; i < n; i++) {
        if (!fast) return -1;  // n > length
        fast = fast->next;
    }
    
    // เคลื่อนทั้งคู่จน fast ถึงท้าย
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow->data;
}

3. 1-indexed vs 0-indexed

ต้องระบุชัดเจนว่า index เริ่มที่ 0 หรือ 1 โค้ดตัวอย่างใช้ 0-indexed

Complexity

• Time: O(N) - worst case ต้องเดินผ่านทั้ง list
• Space: O(1) - ใช้ pointer คงที่

สรุป

การหาโหนดที่ N ใน Linked List เป็นการ traverse ธรรมดา O(N) หากต้องการ query หลายครั้ง ควรพิจารณาแปลงเป็น array/vector หรือใช้ skip list เพื่อให้เข้าถึงได้ O(log N) หรือ O(1)