我已经编写了这段代码两次遍历链表,但是得到了错误的输出。 如何找到已排序链表的中位数?

让我给你一个简单的方法,

  • 取两个指针FastPointer,SlowPointer指向链表的头部
  • 开始两次以FastPointer和SlowPointer的形式遍历链接列表(不要忘记null检查)
  • 如果FastPointer不为null,则将SlowPointer增加1倍。
  • 当FastPointer达到null时,您的SlowPointer指向列表的中间(中间值)。

(注意:在偶数情况下(列表的长度为偶数)计算中位数有点棘手,我留给你,这样你可以考虑一下自己,并提出好的方法)

一切顺利🙂

偶数情况是错误的。 假设n = 6:

123456 < -值
012345 < -指数

那么在您的代码中您将计算mid = n / 2 = 3,但是正如您所看到的,我们要计算索引2和3的值之间的平均值,而在您的代码中,您将查看mid和mid + 1的索引,这是3和4。

因此,在偶数情况下,您应该提前第二步停止遍历(例如,通过设置mid =(count-1)/ 2)。

另外,您有很多重复的代码。 您应将偶数和奇数大小写之间的区别限制为中值的计算(仅是节点的值或两个节点的平均值),但是遍历始终是相同的,因此不应重复。

(编辑:我在这里写过关于野兔/乌龟技巧的文章,但无论如何它已经在问题注释中了。)最后,我忍不住指出,如果保持两个循环,您也可以只使用一个循环来找到中位数列出指针。 一个指针一次执行两个步骤,另一个指针一次执行一个步骤。 当快速指针到达列表的末尾时,慢速指针指向中位数🙂并不是真的更好,但是我喜欢它的原因是您无需计数。

祝好运!

在eCurrent的while循环中,您的温度和eCurrent不匹配(偏移1),从第一个节点本身开始(使eCurrent = head),使temp = 1。
计算列表中的节点数后,请单独检查count == 1,当前代码将给出空指针异常。

正如在问题的评论中提到的使用跑步者的技巧(野兔龟法),它可以为您提供答案,但实现起来很棘手,并且还要检查链表周期。

我能想到的带有最少数量冗余检查的最简单方法(C#标准通用LinkedList的扩展方法):

public static LinkedListNode Middle(this LinkedList self)
{
var node = self.First;
var mid = node;
bool even = false;
while (node.Next != null)
{
if (even)
{
mid = mid.Next;
}
node = node.Next;
even = !even;
}
return mid;
}

注意,我称它为Middle而不是中值,因为LL不一定要排序。 如果您想要一个真实的中位数,请先对列表进行排序,然后再调用中。