如何在链表中找到中间元素 [英] How to find the middle element in linked list

问题描述

在C#中，我需要一个详细的算法，关于如何在链表中找到中间元素. 我检查过Google，所有人都在谈论在列表上平行移动的两个指针. 但是实际上，我找不到该算法的详细解决方案.以及应如何实现这两个指针.

I need a detailed algorithm , in c# about how to find the middle element in linked List. I had checked google and all are talking about the two pointers which moves in parallel over the list . but actually , i couldn't find a detailed solution for the algorithm . and how these two pointers should be implemented .

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

i need the best solution regarding the performance .

推荐答案

这几乎是juharr在单链接列表的注释中建议您的内容.

This is pretty much what juharr suggested you in the comment for singly-linked list.

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

GetMiddle starts at head of the list, rightPointer looks two elements ahead, leftPointer looks at the next element (both pointers move in the same direction). In the end, when there are no more elements to examine, leftPointer is the middle node of the list.

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

In the code below Node is a singly-linked list node, and List just adds elements to the list and exposes its head.

public T GetMiddle<T>(List<T> list)
{
    Node<T> leftPointer = list.Head;
    Node<T> rightPointer = list.Head;

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

    return leftPointer.Item;
}

public class List<T>
{
    public Node<T> Head { get; private set; }
    private Node<T> Last;

    public void Add(T value)
    {
        Node<T> oldLast = Last;
        Last = new Node<T>(value);

        if (Head == null)
        {
            Head = Last;
        }
        else
        {
            oldLast.Next = Last;
        }
    }
}

public class Node<T>
{
    public T Item { get; private set; }
    public Node<T> Next { get; set; }

    public Node(T item)
    {
        Item = item;
    }
}

如果元素数量为偶数，例如[1, 9]

In case of even number of elements, like [1, 9]

var list = new List<int>();
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(我们返回中间).

However, in case of even number of elements, line [1, 10], algorithm will produce 6. That is because when right is at 9, it's next is not null but 10. So when we finish this iteration, right is pointing to null and left is pointing at 6 (which we return as middle).

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

这意味着在偶数情况下，您需要确定将哪个元素作为中间元素-5或6.如果需要5，则循环中将需要一个额外条件:

This means that in even case, you need to decide which element to take as middle - 5 or 6. If you want 5, you will need an extra condition in the loop:

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

这篇关于如何在链表中找到中间元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！