如何在链表中找到中间元素
我需要一个详细的算法,在c#中关于如何在链表中找到中间元素。 我检查了谷歌,所有人都在谈论在列表上并行移动的两个指针。 但实际上,我找不到算法的详细解决方案。 以及如何实施这两个指针。
我需要有关性能的最佳解决方案。
这几乎是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; }
在性能方面找到中间元素的最佳解决方案是计算它:
var mid = list[list.Length/2];
当list.Length
为偶数时,返回中间的元素。
如果你想在list.Length
为偶数时在中间之前返回元素,你可以减少并截断:
上述就是C#学习教程:如何在链表中找到中间元素分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
var mid = list[(int)((list.Length-0.5)/2)];
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1005222.html