Поиск среднего элемента LinkedList в Java — алгоритм двух указателей

Чтобы понять этот пример, сначала ознакомьтесь со следующими темами:

• Класс LinkedList в Java

• Структура данных LinkedList

Пример 1: Получение среднего элемента LinkedList за один проход

class LinkedList {

  // создаём объект класса Node
  // представляет голову связанного списка
  Node head;

  // статический вложенный класс
  static class Node {
    int value;

    // соединяем каждый узел со следующим
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  public static void main(String[] args) {

    // создаём объект LinkedList
    LinkedList linkedList = new LinkedList();

    // присваиваем значения каждому узлу связанного списка
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // соединяем каждый узел связанного списка со следующим
    linkedList.head.next = second;
    second.next = third;

    // печатаем связанный список
    Node pointer = linkedList.head;
    System.out.print("LinkedList: " );
    while (pointer != null) {
      System.out.print(pointer.value + " ");
      pointer = pointer.next;
    }

    // Находим средний элемент
    Node ptr1 = linkedList.head;
    Node ptr2 = linkedList.head;

    while (ptr1.next != null) {

      // увеличиваем ptr1 на 2, а ptr2 на 1
      // если ptr1 указывает на последний элемент
      // ptr2 будет указывать на средний элемент
      ptr1 = ptr1.next;
      if(ptr1.next !=null) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
      }
    }

    System.out.println("\nMiddle Element: " + ptr2.value);

  }
}

Вывод:

LinkedList: 1 2 3
Middle Element: 2

В примере выше мы реализовали структуру данных связанный список в Java. Затем мы находим средний элемент связанного списка за один цикл. Обратите внимание на код:

while (ptr1.next != null) {

  // увеличиваем ptr1 на 2, а ptr2 на 1
  // если ptr1 указывает на последний элемент
  // ptr2 будет указывать на средний элемент
  ptr1 = ptr1.next;
  if(ptr1.next !=null) {
    ptr1 = ptr1.next;
    ptr2 = ptr2.next;
  }
}

Здесь у нас есть две переменные ptr1 и ptr2. Мы используем эти переменные, чтобы пройти по связанному списку.

На каждой итерации ptr1 будет обращаться к двум узлам, а ptr2 — к одному узлу связанного списка.

Теперь, когда ptr1 достигнет конца связанного списка, ptr2 будет в середине. Таким образом, мы можем получить середину связанного списка за одну итерацию.

Пример 2: Получение среднего элемента LinkedList с помощью класса LinkedList

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // создаём связанный список с помощью класса LinkedList
    LinkedList<String> animals = new LinkedList<>();

    // добавляем элементы в LinkedList
    animals.add("Dog");
    animals.addFirst("Cat");
    animals.addLast("Horse");
    System.out.println("LinkedList: " + animals);

    // получаем средний элемент
    String middle = animals.get(animals.size()/2);
    System.out.println("Middle Element: " + middle);
    }
}

Вывод:

LinkedList: [Cat, Dog, Horse]
Middle Element: Dog

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

animals.get(animals.size()/2)

• size()/2 — возвращает позицию среднего элемента

• get() — возвращает элемент в средней позиции

---