在 C++ 中查找有序链表中的中位数
c++server side programmingprogramming更新于 2025/3/15 11:37:17
在这个问题中，我们给出了一个由 N 个元素组成的有序链表。我们的任务是查找有序链表中的中位数。
有序链表是一个简单的链表，其中所有元素都按特定顺序排序。示例 − 4 -> 6 -> 7 -> 9 -> NULL
中位数是链表的中间元素。如果 N 为奇数，则中位数为第 (n/2) 个元素
如果 N 为偶数，则中位数为第 (n/2) 个元素和第 (n/2 + 1) 个元素的平均值。
我们举一个例子来理解这个问题，
输入：2 -> 3 -> 4 -> 6 -> 9 -> NULL 输出：4
解决方法
这个问题的一个简单解决方法是通过遍历链表来计算链表的所有元素。
现在，如果计数为奇数，我们将再次遍历链表，直到链表的第 N/2 个元素。
如果计数为偶数，我们将遍历到第 N/2 个元素和第 N/2 + 1 个元素，将它们相加并除以 2。
替代方法
解决问题的另一种方法是使用双指针遍历链表并找到链表元素的数量。
这是一个在不计算元素数量的情况下找到中位数的算法。它们有两个指针pointer1和pointer2，根据条件，我们可以得到，
如果pointer1不为NULL，pointer2就是中位数。
如果pointer1为NULL，则（pointer2的上一个节点+pointer2->数据）/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<<"链表的中位数是";
findMedianValue(head);
return 0;
}
输出
链表的中位数是 7
