इस समस्या में, हमें N तत्वों से युक्त एक क्रमबद्ध लिंक्ड सूची दी गई है। हमारा काम एक क्रमबद्ध लिंक्ड सूची में माध्यिका खोजना . है ।
सॉर्ट की गई लिंक की गई सूची एक साधारण लिंक्ड सूची है जिसमें सभी तत्वों को एक विशिष्ट क्रम में क्रमबद्ध किया जाता है। उदाहरण -4 -> 6 -> 7 -> 9 -> NULL
माध्यिका लिंक्ड सूची का मध्य तत्व है। यह पाया जा सकता है जैसे N विषम है:माध्यिका है (n/2) th तत्व
यदि N सम है -s माध्यिका (n/2) th . का औसत है तत्व और (n/2 + 1) वें तत्व।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
समाधान दृष्टिकोण
समस्या का एक सरल समाधान लिंक की गई सूची के सभी तत्वों को ट्रैवर्स करके गिनना है।
अब, यदि गिनती विषम है, तो हम फिर से लिंक की गई सूची को लिंक की गई सूची के N/2वें तत्व तक पार करेंगे।
अगर गिनती सम है, तो हम N/2वें तत्व और N/2 + 1वें तत्व तक जाएंगे, उन्हें जोड़ेंगे और 2 से विभाजित करेंगे।
वैकल्पिक दृष्टिकोण
समस्या को हल करने का एक और तरीका है, दो पॉइंटर ट्रैवर्सल का उपयोग करके लिंक की गई सूची को ट्रेस करना और लिंक की गई सूची के तत्वों की संख्या का पता लगाना।
यहां तत्वों की संख्या की गणना किए बिना माध्यिका खोजने के लिए एक एल्गोरिथ्म है। उनके दो पॉइंटर्स पॉइंटर1 और पॉइंटर2 हैं, जो स्थिति के आधार पर हमारे पास हो सकते हैं,
यदि पॉइंटर1 NULL नहीं है, तो पॉइंटर2 माध्यिका है।
यदि पॉइंटर 1 NULL है, तो (पॉइंटर 2 के नोड + पॉइंटर 2 -> डेटा के पिछले)/2।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#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;
} आउटपुट
The median of the linked list is 7