数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找排序链表的中位数
在这个问题中，我们给定一个包含 N 个元素的排序链表。我们的任务是查找排序链表的中位数。
排序链表是一个简单的链表，其中所有元素都按特定顺序排序。示例 - 4 -> 6 -> 7 -> 9 -> NULL
中位数是链表的中间元素。如果 N 是奇数，则可以将其找到为：中位数是第 (n/2)th 个元素
如果 N 是偶数 - 中位数是第 (n/2)th 个元素和第 (n/2 + 1)th 个元素的平均值。
让我们举个例子来理解这个问题，
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
解决方案方法
解决此问题的一个简单方法是通过遍历链表来计算所有元素。
现在，如果计数为奇数，我们将再次遍历链表，直到链表的第 N/2 个元素。
如果计数为偶数，我们将遍历到第 N/2 个元素和第 N/2 + 1 个元素，将它们加起来再除以 2。
替代方法
解决此问题的另一种方法是使用双指针遍历链表并找到链表中元素的计数。
以下是如何在不计算元素数量的情况下查找中位数的算法。有两个指针 pointer1 和 pointer2，根据条件，我们可以有：
如果 pointer1 不为空，则 pointer2 是中位数。
如果 pointer1 为空，则 (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
更新于: 2022年2月1日
384 次查看
广告