如何只用一次迭代找到链表中的四分位数

Question

我有一个整数单链表。节点定义为

class Node {
public:
int value;
Node *next = NULL;
};

我需要分别找到q1,q2和q3(第一，第二和第三四分位数)。使用两次遍历很容易找到，因为第一次遍历查找链表的长度，第二次遍历查找确切的元素。但是如何通过对链表的一次遍历来找到它呢?为了找到q2(中位数)，我们可以使用慢速和快速指针方法。在每次迭代中，我们将一个指针增加到一步，第二个指针增加到两步。在这种情况下，我们将得到链表的一半大小的位置。

但是如何找到q1和q3呢?我已经编写了代码来查找中位数(q2)

void findQuartiles(Node *head)
{
Node *q2 = head;
Node *temp = head;
int q2_data;
while(temp)
{
q2_data = q2->value;
q2 = q2->next;
temp = temp->next->next;
}
cout<<"nq2 = "<<q2_data;
}

这段代码是用c++编写的。如果你能在其他语言上也帮助我，那就好了。

Answer 1

我不知道最好的解决方案是什么，但我个人会创建一个链接列表包装器，看起来像下面(C语言):

//Individual node    
struct linked_list_node {
void * data;
struct list_node next;
};

//List wrapper. Can contain more useful data about the list.
struct linked_list {
struct _private_node *head;
struct _private_node *tail;
int count;
};

您不需要在包装器中包含尾部，但是以0(1)的速度实现追加函数是有用的，并且它不会占用太多内存。添加一个用于计算道具数量的变量将让你一次就找到四分位数。通过计数，您已经可以知道中位数和四分位数节点将是什么，为每个节点准备变量，然后遍历列表一次以找到每个特定节点的地址。如果你的数据是数值，你会想要使用双精度，因为如果你需要计算中位数的实际值，而你有一个偶数，你必须计算平均值，并且有一个机会得到0.5。