如何在链表中找到中间元素

我需要一个详细的算法，在c＃中关于如何在链表中找到中间元素。 我检查了谷歌，所有人都在谈论在列表上并行移动的两个指针。 但实际上，我找不到算法的详细解决方案。 以及如何实施这两个指针。

我需要有关性能的最佳解决方案。

Answer 1

这几乎是juharr在单链表的评论中建议你的。

GetMiddle从列表的头部开始， rightPointer两个元素， leftPointer查看下一个元素（两个指针都朝同一方向移动）。 最后，当没有更多要检查的元素时， leftPointer是列表的中间节点。

在下面的代码中， Node是一个单链接列表节点， List只是将元素添加到列表中并公开其head 。

 public T GetMiddle(List list) { Node leftPointer = list.Head; Node rightPointer = list.Head; while (rightPointer != null && rightPointer.Next != null) { rightPointer = rightPointer.Next.Next; leftPointer = leftPointer.Next; } return leftPointer.Item; } public class List { public Node Head { get; private set; } private Node Last; public void Add(T value) { Node oldLast = Last; Last = new Node(value); if (Head == null) { Head = Last; } else { oldLast.Next = Last; } } } public class Node { public T Item { get; private set; } public Node Next { get; set; } public Node(T item) { Item = item; } } 

在偶数个元素的情况下，如[1, 9]

 var list = new List(); foreach (var number in Enumerable.Range(1, 9)) { list.Add(number); } Console.WriteLine(GetMiddle(list)); 

中间元素是5 。

但是，在偶数个元素的情况下，行[1, 10] ，算法将产生6 。 那是因为当right是9 ，它的下一个不是null而是10 。 所以当我们完成这个迭代时， right指向null而left指向6 （我们返回中间）。

 right: 1 -> 3 -> 5 -> 7 -> 9 -> null | end left: 1 -> 2 -> 3 -> 4 -> 5 -> 6 | end 

这意味着在偶数情况下，你需要决定采用哪个元素作为中间 – 5或6.如果你想要5，你需要在循环中有一个额外的条件：

 rightPointer = rightPointer.Next.Next; if (rightPointer != null) { leftPointer = leftPointer.Next; } 

Answer 2

在性能方面找到中间元素的最佳解决方案是计算它：

 var mid = list[list.Length/2]; 

当list.Length为偶数时，返回中间的元素。

如果你想在list.Length为偶数时在中间之前返回元素，你可以减少并截断：

 var mid = list[(int)((list.Length-0.5)/2)];