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));
}


LinkedList

クラスの内部コードを確認すると、この例では、中央の要素に到達するまでリストを調べているだけです。

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つの方法は、再帰を使用することです。サイズを知るためにリストの最後まで繰り返すことができます。** コールバックでは、サイズの半分までカウントします。

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でリンクリストの中間要素を見つけるという問題を紹介し、それを解決するさまざまな方法を示しました。

サイズを追跡する最も単純な方法から始めました。その後、リストのヘッドノードから中央の要素を見つけるための解決策を続けました。

いつものように、例の完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[GitHubで利用可能]です。