ในปัญหานี้ เราได้รับรายการที่เชื่อมโยงที่เรียงลำดับซึ่งประกอบด้วยองค์ประกอบ N งานของเราคือ ค้นหาค่ามัธยฐานในรายการที่เชื่อมโยงที่เรียงลำดับแล้ว .
จัดเรียงรายการเชื่อมโยง เป็นรายการที่เชื่อมโยงอย่างง่ายซึ่งองค์ประกอบทั้งหมดจะถูกจัดเรียงตามลำดับเฉพาะ ตัวอย่าง − 4 -> 6 -> 7 -> 9 -> NULL
ค่ามัธยฐาน เป็นองค์ประกอบกลางของรายการที่เชื่อมโยง หาได้เหมือนกับว่า N เป็นเลขคี่ :ค่ามัธยฐานคือ (n/2) th องค์ประกอบ
ถ้า N เป็นคู่ −s มัธยฐานคือค่าเฉลี่ยของ (n/2) th องค์ประกอบและ (n/2 + 1) th ธาตุ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการนับองค์ประกอบทั้งหมดของรายการที่เชื่อมโยงโดยข้ามผ่านมัน
ตอนนี้ หากการนับเป็นเลขคี่ เราจะสำรวจรายการที่เชื่อมโยงอีกครั้งจนถึงองค์ประกอบ N/2 ของรายการที่เชื่อมโยง
หากการนับเป็นเลขคู่ เราจะสำรวจจนถึงองค์ประกอบที่ N/2 และองค์ประกอบที่ N/2 + 1 บวกเข้าด้วยกันแล้วหารด้วย 2
แนวทางอื่น
อีกแนวทางหนึ่งในการแก้ปัญหาคือการสำรวจรายการที่เชื่อมโยงโดยใช้การข้ามผ่านตัวชี้สองตัวและค้นหาการนับองค์ประกอบของรายการที่เชื่อมโยง
นี่คืออัลกอริทึมในการค้นหาค่ามัธยฐานโดยไม่นับจำนวนองค์ประกอบ พวกมันคือพอยน์เตอร์สองตัวพอยน์เตอร์1 และพอยน์เตอร์2 ตามเงื่อนไขที่เราสามารถมีได้
หากตัวชี้ 1 ไม่ใช่ค่า NULL แสดงว่าตัวชี้ 2 มีค่ามัธยฐาน
ถ้า pointer1 เป็น NULL ดังนั้น (ก่อนหน้าของโหนดของ pointer2 + pointer2 -> data)/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
