Trong bài toán này, chúng ta được đưa ra một danh sách liên kết đã sắp xếp gồm N phần tử. Nhiệm vụ của chúng tôi là tìm Trung vị trong Danh sách được Liên kết Đã sắp xếp .
Danh sách được liên kết được sắp xếp là một danh sách liên kết đơn giản, trong đó tất cả các phần tử được sắp xếp theo một thứ tự cụ thể. Ví dụ - 4 -> 6 -> 7 -> 9 -> KHÔNG ĐỦ
Trung vị là các phần tử giữa của danh sách liên kết. Nó có thể được tìm thấy như thể N là số lẻ:trung vị là (n / 2) th phần tử
nếu N chẵn thì trung vị là trung bình của (n / 2) th phần tử và (n / 2 + 1) th phần tử.
Hãy lấy một ví dụ để hiểu vấn đề,
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là đếm tất cả các phần tử của danh sách được liên kết bằng cách duyệt qua nó.
Bây giờ, nếu số lượng là số lẻ, chúng tôi sẽ duyệt lại danh sách được liên kết cho đến phần tử thứ N / 2 của danh sách được liên kết.
Nếu số đếm là chẵn, chúng ta sẽ duyệt cho đến phần tử thứ N / 2 và phần tử thứ N / 2 + 1, cộng chúng và chia cho 2.
Phương pháp thay thế
Một cách tiếp cận khác để giải quyết vấn đề, là bằng cách duyệt qua danh sách được liên kết bằng cách sử dụng phép duyệt hai con trỏ và tìm số phần tử của danh sách được liên kết.
Đây là một thuật toán để tìm giá trị trung bình mà không cần đếm số phần tử. Chúng là hai con trỏ pointer1 và pointer2, dựa trên điều kiện, chúng ta có thể có,
Nếu con trỏ1 không phải là NULL, con trỏ 2 là trung vị.
Nếu con trỏ1 là NULL, thì (trước nút của con trỏ2 + con trỏ2 -> dữ liệu) / 2.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void findMedianValue(Node* head){
Node* ptr1 = head;
Node* ptr2 = head;
Node* prev = head;
if (head != NULL) {
while (ptr2 != NULL && ptr2->next != NULL) {
ptr2 = ptr2->next->next;
prev = ptr1;
ptr1 = ptr1->next;
}
if (ptr2 != NULL)
cout<<ptr1->data;
else
cout<<float(ptr1->data + prev->data) / 2;
}
}
void pushVal(struct 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 main(){
struct Node* head = NULL;
pushVal(&head, 3);
pushVal(&head, 5);
pushVal(&head, 6);
pushVal(&head, 8);
pushVal(&head, 9);
pushVal(&head, 11);
cout<<"The median of the linked list is ";
findMedianValue(head);
return 0;
} Đầu ra
The median of the linked list is 7