Tìm trung vị trong danh sách liên kết đã sắp xếp C++

Mô tả bài toán

Cho linked list đã sắp xếp. Tìm trung vị: nếu N lẻ → phần tử giữa; nếu chẵn → trung bình 2 phần tử giữa.

Ví dụ

2→3→4→6→9→NULL → Output: 4.

Giải thuật (Hai con trỏ)

Dùng slow, fast. fast nhảy 2 bước, slow nhảy 1 bước. Khi fast hết:\n- fast != NULL (N lẻ) → slow là trung vị.\n- fast == NULL (N chẵn) → trung vị = (slow->data + prev->data)/2.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

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

void findMedianValue(Node* head) {
    Node *slow=head, *fast=head, *prev=head;
    if (!head) return;
    while (fast && fast->next) {
        fast = fast->next->next;
        prev = slow;
        slow = slow->next;
    }
    if (fast) cout << slow->data;       // odd
    else cout << float(slow->data + prev->data)/2; // even
}

void push(Node** head, int val) {
    Node* n = new Node{val, *head};
    *head = n;
}

int main() {
    Node* head=null;
    push(&head,3); push(&head,5); push(&head,6); push(&head,8);
    push(&head,9); push(&head,11);
    cout << "Median: "; findMedianValue(head);
    return 0;
}

Đầu ra

The median of the linked list is 7