Tìm nút thứ k từ giữa về đầu danh sách liên kết trong C++

Cho danh sách liên kết và số k. Nhiệm vụ: tìm nút thứ k từ giữa về phía đầu.

Ví dụ:

Đầu vào: linked-list: 4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k = 2

Đầu ra: 7

Giải thích:

Nút giữa giá trị 9. Nút thứ 2 từ giữa về đầu là 7.

Phương pháp giải

Đếm độ dài n của danh sách. Nút giữa ở vị trí n/2 + 1 (1-based). Nút cần tìm ở vị trí (n/2 + 1 - k) từ đầu. Duyệt đến vị trí đó.

Chương trình minh họa

Ví dụ

#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;
    }
}

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;
}

Kết quả

2th element from beginning towards head is 7