1. 概要

このチュートリアルでは、Javaでリンクリストの中央の要素を見つける方法を説明します。

次のセクションでは主な問題を紹介し、それらを解決するためのさまざまなアプローチを示します。

2. サイズを追跡する

この問題は、リストに新しい要素を追加するときにサイズを追跡するだけで簡単に解決できます。 サイズがわかれば、真ん中の要素がどこにあるかもわかっているので、解決策は簡単です。

LinkedListのJava実装を使用した例を見てみましょう。

public static Optional<String> findMiddleElementLinkedList(
  LinkedList<String> linkedList) {
    if (linkedList == null || linkedList.isEmpty()) {
        return Optional.empty();
    }

    return Optional.of(linkedList.get(
      (linkedList.size() - 1) / 2));
}

LinkedInList クラスの内部コードを確認すると、この例では、真ん中の要素に到達するまでリストをトラバースしていることがわかります。

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }
}

3. サイズを知らずに真ん中を見つける

リンクリストのヘッドノードしかなく、中央の要素を見つける必要があるという問題が発生することはよくあることです。 この場合、リストのサイズがわからないため、この問題の解決が難しくなります。

次のセクションでは、この問題を解決するためのいくつかのアプローチを示しますが、最初に、リストのノードを表すクラスを作成する必要があります。

String値を格納するNodeクラスを作成しましょう。

public static class Node {

    private Node next;
    private String data;

    // constructors/getters/setters
  
    public boolean hasNext() {
        return next != null;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public String toString() {
        return this.data;
    }
}

また、テストケースでこのヘルパーメソッドを使用して、ノードのみを使用して単一リンクリストを作成します。

private static Node createNodesList(int n) {
    Node head = new Node("1");
    Node current = head;

    for (int i = 2; i <= n; i++) {
        Node newNode = new Node(String.valueOf(i));
        current.setNext(newNode);
        current = newNode;
    }

    return head;
}

3.1. 最初にサイズを見つける

この問題に取り組む最も簡単なアプローチは、最初にリストのサイズを見つけ、その後、前に使用したのと同じアプローチに従って、中央の要素まで反復することです。

このソリューションの動作を見てみましょう。

public static Optional<String> findMiddleElementFromHead(Node head) {
    if (head == null) {
        return Optional.empty();
    }

    // calculate the size of the list
    Node current = head;
    int size = 1;
    while (current.hasNext()) {
        current = current.next();
        size++;
    }

    // iterate till the middle element
    current = head;
    for (int i = 0; i < (size - 1) / 2; i++) {
        current = current.next();
    }

    return Optional.of(current.data());
}

ご覧のとおり、 このコードはリストを2回繰り返します。 したがって、このソリューションのパフォーマンスは低く、お勧めできません

3.2. ワンパスで中間要素を繰り返し見つける

リスト上で1回だけ反復する中央の要素を見つけることにより、前のソリューションを改善します。

これを繰り返し行うには、リストを同時に繰り返すための2つのポインターが必要です。 1つのポインターは各反復で2ノードを前進させ、もう1つのポインターは反復ごとに1つのノードのみを前進させます

速いポインタがリストの最後に達すると、遅いポインタが中央になります。

public static Optional<String> findMiddleElementFromHead1PassIteratively(Node head) {
    if (head == null) {
        return Optional.empty();
    }

    Node slowPointer = head;
    Node fastPointer = head;

    while (fastPointer.hasNext() && fastPointer.next().hasNext()) {
        fastPointer = fastPointer.next().next();
        slowPointer = slowPointer.next();
    }

    return Optional.ofNullable(slowPointer.data());
}

このソリューションは、奇数と偶数の両方の要素を持つリストを使用した単純な単体テストでテストできます。

@Test
public void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() {
 
    assertEquals("3", MiddleElementLookup
      .findMiddleElementFromHead1PassIteratively(
        createNodesList(5)).get());
    assertEquals("2", MiddleElementLookup
      .findMiddleElementFromHead1PassIteratively(
        reateNodesList(4)).get());
}

3.3. 1つのパスで中間要素を再帰的に見つける

この問題を1回のパスで解決する別の方法は、再帰を使用することです。 リストの最後まで繰り返してサイズを知ることができ、コールバックでは、サイズの半分までカウントします。

Javaでこれを行うには、すべての再帰呼び出しの実行中にリストサイズと中間要素の参照を保持する補助クラスを作成します。

private static class MiddleAuxRecursion {
    Node middle;
    int length = 0;
}

それでは、再帰メソッドを実装しましょう。

private static void findMiddleRecursively(
  Node node, MiddleAuxRecursion middleAux) {
    if (node == null) {
        // reached the end
        middleAux.length = middleAux.length / 2;
        return;
    }
    middleAux.length++;
    findMiddleRecursively(node.next(), middleAux);

    if (middleAux.length == 0) {
        // found the middle
        middleAux.middle = node;
    }
    
    middleAux.length--;
}

そして最後に、再帰的なメソッドを呼び出すメソッドを作成しましょう。

public static Optional<String> findMiddleElementFromHead1PassRecursively(Node head) {
 
    if (head == null) {
        return Optional.empty();
    }

    MiddleAuxRecursion middleAux = new MiddleAuxRecursion();
    findMiddleRecursively(head, middleAux);
    return Optional.of(middleAux.middle.data());
}

繰り返しますが、以前と同じ方法でテストできます。

@Test
public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() {
    assertEquals("3", MiddleElementLookup
      .findMiddleElementFromHead1PassRecursively(
        createNodesList(5)).get());
    assertEquals("2", MiddleElementLookup
      .findMiddleElementFromHead1PassRecursively(
        createNodesList(4)).get());
}

4. 結論

この記事では、Javaでリンクリストの中間要素を見つける問題を紹介し、それを解決するさまざまな方法を示しました。

サイズを追跡する最も単純なアプローチから始め、その後、リストのヘッドノードから中央の要素を見つけるためのソリューションを続けました。

いつものように、例の完全なソースコードは、GitHubから入手できます。