data-structures - リンクされたリストの中間要素を見つけるにはどうすればよいですか?

Question

リスト全体を 1 回だけトラバースして、リンクされたリストの中間要素を見つけるにはどうすればよいですか?

リストの長さは指定されておらず、使用できるポインターは 2 つだけです。これはどのように行うことができますか？

Answer 1

以下のコードは、中間要素を取得するのに役立ちます。「高速」と「低速」の 2 つのポインターを使用する必要があります。各ステップで、高速ポインタは 2 ずつ増加し、低速ポインタは 1 ずつ増加します。リストが終了すると、スロー ポインターは中央になります。

Nodeこのような外観を考えてみましょう

class Node
{
  int data;
  Node next;
}

また、LinkedList には、リンクされたリストの先頭を提供するゲッター メソッドがあります。

public Node getHead()
{
  return this.head;
}

以下のメソッドは、リストの中央の要素を取得します (リストのサイズを知らなくても)

public int getMiddleElement(LinkedList l)
{
    return getMiddleElement(l.getHead());
}

private int getMiddleElement(Node n)
{
    Node slow = n;
    Node fast = n;

    while(fast!=null && fast.next!=null)
    {
        fast = fast.next.next;
        slow = slow.next;
    }

    return slow.data;
}

例:
リストが 1-2-3-4-5 の場合、中央の要素は 3
リストが 1-2-3-4 の場合、中央の要素は 3

Answer 2

C では、完全を期すためにポインターを使用します。これは、リンクされたリストにサイクルが含まれているかどうかをチェックするために使用される" Tortoise and Hare " アルゴリズムに基づいていることに注意してください。

ノードは次のように定義されます。

typedef struct node {
    int          val;
    struct node *next;
} node_t;

したがって、アルゴリズムは次のようになります。

node_t *
list_middle (node_t *root)
{
    node_t *tort = root;
    node_t *hare = root;

    while (hare != NULL && hare->next != NULL) {
        tort = tort->next;
        hare = hare->next->next;
    }

    return (tort);
}

偶数のノードを持つリストの場合、これは実際の中心に進むノードを返します (たとえば、10 個のノードのリストでは、これはノード 6 を返します)。

Answer 3

C# を使用して、リンクされたリストの中間要素を見つけます。

static void Main(string[] args)
{
    LinkedList<int> linked = new LinkedList<int>();
    linked.AddLast(1);
    linked.AddLast(3);
    linked.AddLast(5);
    linked.AddLast(6);
    linked.AddFirst(12);

    Console.WriteLine("Middle Element - " + ListMiddle<int>(linked));
    Console.ReadLine();
}

public static T ListMiddle<T>(IEnumerable<T> input)
{
    if (input == null)
        return default(T);

    var slow = input.GetEnumerator();
    var fast = input.GetEnumerator();

    while (slow.MoveNext())
    {
        if (fast.MoveNext())
        {
            if (!fast.MoveNext())
                return slow.Current;
        }
        else
        {
            return slow.Current;
        }
    }
    return slow.Current;
}