ในปัญหานี้ เราได้รับ linked list ที่จัดเรียงแล้วประกอบด้วย N องค์ประกอบ ภารกิจของเราคือ หาค่า Median ใน Linked List ที่จัดเรียงแล้ว
Sorted Linked List คือ linked list ธรรมดาที่องค์ประกอบทั้งหมดจัดเรียงในลำดับเฉพาะ ตัวอย่าง - 4 -> 6 -> 7 -> 9 -> NULL
Median คือองค์ประกอบกลางของ linked list สามารถหาได้ว่า ถ้า N เป็นคี่ : median คือ (n/2)th องค์ประกอบ
ถ้า N เป็นคู่ - median คือค่าเฉลี่ยของ (n/2)th องค์ประกอบและ (n/2 + 1)th องค์ประกอบ
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการนับองค์ประกอบทั้งหมดของ linked list โดยการเดินทางผ่านมัน
ตอนนี้ ถ้าจำนวนเป็นคี่ เราจะเดินทางผ่าน linked list อีกครั้งจนถึงองค์ประกอบ N/2 ของ linked list
ถ้าจำนวนเป็นคู่ เราจะเดินทางจนถึงองค์ประกอบ N/2 และ N/2 + 1 บวกพวกมันแล้วหาร 2
วิธีทางเลือก
อีกวิธีหนึ่งในการแก้ปัญหา คือการเดินทางผ่าน linked list โดยใช้ two pointer traversal และหาจำนวนองค์ประกอบของ linked list
นี่คืออัลกอริทึมเพื่อหา median โดยไม่ต้องนับจำนวนองค์ประกอบ มีตัวชี้สองตัว pointer1 และ pointer2 ตามเงื่อนไข เราสามารถได้ว่า
ถ้า pointer1 ไม่ใช่ NULL pointer2 คือ median
ถ้า pointer1 เป็น NULL แล้ว (previous of node of 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
