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

1. Обзор

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

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

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

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

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

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

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

Если мы проверим внутренний код класса LinkedList , мы увидим, что в этом примере мы просто проходим по списку, пока не достигнем среднего элемента:

Node node(int index) {
    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    } else {
        Node 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 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 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 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 .