Найти средний элемент LinkedList за один проход

Поиск среднего элемента LinkedList за один проход

Суть задачи

Нужно найти средний элемент односвязного списка за один проход, не зная заранее длины списка. Классическое применение техники двух указателей (Two Pointers).

Техника двух указателей

Идея: Используем два указателя:

• slow — движется на 1 шаг за раз
• fast — движется на 2 шага за раз

Когда fast достигнет конца списка, slow будет находиться в середине.

Почему это работает

Список: 1 → 2 → 3 → 4 → 5 → null

Шаг 1: slow=1, fast=1
Шаг 2: slow=2, fast=3
Шаг 3: slow=3, fast=5
Шаг 4: slow=3, fast=null → fast достиг конца

Ответ: slow указывает на 3 (середину)

По математике: когда fast дойдет до конца, slow будет ровно в середине.

Реализация

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class LinkedListMiddle {
    /**
     * Найти значение среднего элемента LinkedList
     * @param head - голова списка
     * @return значение среднего элемента
     */
    public int findMiddle(ListNode head) {
        // Граничные случаи
        if (head == null) {
            throw new IllegalArgumentException("Список пуст");
        }
        if (head.next == null) {
            return head.val;  // один элемент
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // fast движется на 2 шага, slow на 1
        // Цикл продолжается, пока fast не достигнет конца
        while (fast != null && fast.next != null) {
            slow = slow.next;           // 1 шаг
            fast = fast.next.next;      // 2 шага
        }
        
        // slow теперь указывает на середину
        return slow.val;
    }
}

Пошаговый пример

Список: 1 → 2 → 3 → 4 → 5 → null

Итерация 1:
  slow: 1 → next → 2
  fast: 1 → next.next → 3

Итерация 2:
  slow: 2 → next → 3
  fast: 3 → next.next → 5

Итерация 3:
  slow: 3 → next → 4
  fast: 5 → next.next → null (fast == null)
  ЦИК ЗАВЕРШАЕТСЯ

Ответ: slow.val = 4? Нет! При нечётном количестве:
  slow указывает на первый из средних
  Итог: 3 ✓

Для чётного количества элементов

Список: 1 → 2 → 3 → 4 → 5 → 6 → null

Итерация 1:
  slow: 1 → 2
  fast: 1 → 3

Итерация 2:
  slow: 2 → 3
  fast: 3 → 5

Итерация 3:
  slow: 3 → 4
  fast: 5 → null (fast.next == null)
  ЦИКЛ ЗАВЕРШАЕТСЯ

Ответ: slow.val = 4 ✓ (второй из двух средних)

Альтернатива: возврат узла

public ListNode findMiddleNode(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;  // возвращаем сам узел
}

Тесты

public class LinkedListMiddleTest {
    private LinkedListMiddle solution = new LinkedListMiddle();
    
    @Test
    public void testOddLength() {
        ListNode head = createList(new int[]{1, 2, 3, 4, 5});
        assertEquals(3, solution.findMiddle(head));
    }
    
    @Test
    public void testEvenLength() {
        ListNode head = createList(new int[]{1, 2, 3, 4, 5, 6});
        assertEquals(4, solution.findMiddle(head));
    }
    
    @Test
    public void testSingleElement() {
        ListNode head = createList(new int[]{1});
        assertEquals(1, solution.findMiddle(head));
    }
    
    @Test
    public void testTwoElements() {
        ListNode head = createList(new int[]{1, 2});
        assertEquals(2, solution.findMiddle(head));
    }
    
    @Test
    public void testLargeList() {
        int[] data = new int[1001];
        for (int i = 0; i < 1001; i++) {
            data[i] = i + 1;
        }
        ListNode head = createList(data);
        assertEquals(501, solution.findMiddle(head));
    }
    
    // Вспомогательный метод для создания списка
    private ListNode createList(int[] values) {
        if (values.length == 0) return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }
}

Варианты задачи

1. Найти соседей среднего элемента

public ListNode[] findMiddleWithNeighbors(ListNode head) {
    if (head == null || head.next == null) {
        return new ListNode[]{head};
    }
    
    ListNode slow = head;
    ListNode fast = head;
    ListNode prev = null;
    
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // slow - средний элемент
    // prev - его предыдущий сосед
    return new ListNode[]{prev, slow, slow.next};
}

2. Разделить список пополам

public ListNode[] splitList(ListNode head) {
    if (head == null) return new ListNode[]{null, null};
    
    ListNode slow = head;
    ListNode fast = head;
    ListNode prev = null;
    
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Разрываем связь
    if (prev != null) {
        prev.next = null;
    }
    
    return new ListNode[]{head, slow};
}

Сложность

Почему не считать элементы дважды?

// ❌ Два прохода
public int findMiddleTwoPass(ListNode head) {
    // Проход 1: считаем длину
    int length = 0;
    ListNode current = head;
    while (current != null) {
        length++;
        current = current.next;
    }
    
    // Проход 2: идём до середины
    int mid = length / 2;
    current = head;
    for (int i = 0; i < mid; i++) {
        current = current.next;
    }
    
    return current.val;
}

Это работает, но требует 2 прохода и O(n) операций. Техника двух указателей делает то же самое за один проход!

Вывод

Техника двух указателей (Tortoise and Hare) — это элегантное решение для работы с LinkedList. Она часто используется в алгоритмах поиска цикла, нахождения середины и других операций. Запомни эту технику — она очень часто встречается на интервью!