«Найдите средний элемент связанного списка в Java»

«1. Обзор

В этом руководстве мы объясним, как найти средний элемент связанного списка в Java.

В следующих разделах мы представим основные проблемы и покажем различные подходы к их решению.

2. Отслеживание размера

Эту проблему можно легко решить, просто отслеживая размер при добавлении новых элементов в список. Если мы знаем размер, мы также знаем, где находится средний элемент, поэтому решение тривиально.

Давайте рассмотрим пример с использованием Java-реализации LinkedList:

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. Поиск середины без знания размера

Очень часто мы сталкиваемся с проблемами, когда у нас есть только головной узел связанного списка, и нам нужно найти средний элемент. В этом случае мы не знаем размер списка, что усложняет решение этой проблемы.

В следующих разделах мы покажем несколько подходов к решению этой проблемы, но сначала нам нужно создать класс для представления узла списка.

Давайте создадим класс Node, в котором хранятся значения String:

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

Как мы видим, этот код выполняет итерацию по списку дважды. Поэтому это решение имеет низкую производительность и не рекомендуется.

3.2. Итеративный поиск среднего элемента за один проход

Теперь мы улучшим предыдущее решение, найдя средний элемент всего за одну итерацию по списку.

Чтобы сделать это итеративно, нам нужны два указателя для одновременного прохода по списку. Один указатель будет продвигать 2 узла за каждую итерацию, а другой указатель будет продвигать только один узел за итерацию.

Когда более быстрый указатель достигнет конца списка, более медленный указатель окажется в середине:

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. Рекурсивный поиск среднего элемента за один проход

Другой способ решить эту проблему за один проход — использовать рекурсию. Мы можем выполнить итерацию до конца списка, чтобы узнать размер, и в обратных вызовах мы просто считаем до половины размера.

Чтобы сделать это в 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.