Развернуть LinkedList

Развёртывание LinkedList

Суть задачи

Преобразовать порядок элементов в списке на противоположный: первый становится последним, второй — предпоследним и т.д. Это делается путём изменения направления указателей next.

Идея решения

У каждого узла есть указатель next. Нужно развернуть эти указатели в противоположном направлении:

Исходный список:  1 → 2 → 3 → null
Развёрнутый:      null ← 1 ← 2 ← 3

Итеративная реализация (O(1) память)

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

public class ReverseLinkedList {
    /**
     * Развернуть список, используя три указателя
     * @param head - голова исходного списка
     * @return новая голова (старый хвост)
     */
    public ListNode reverse(ListNode head) {
        ListNode prev = null;      // предыдущий узел
        ListNode current = head;   // текущий узел
        
        while (current != null) {
            // Сохраняем следующий узел перед изменением связи
            ListNode next = current.next;
            
            // Разворачиваем указатель: current.next теперь указывает назад
            current.next = prev;
            
            // Сдвигаемся на шаг вперёд
            prev = current;
            current = next;
        }
        
        return prev;  // новая голова (старый хвост)
    }
}

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

Исходный список: 1 → 2 → 3 → null

Итерация 1:
  next = 2 → 3 → null (сохранили)
  1.next = null (развернули)
  prev = 1, current = 2

Итерация 2:
  next = 3 → null (сохранили)
  2.next = 1 (развернули)
  prev = 2, current = 3

Итерация 3:
  next = null (сохранили)
  3.next = 2 (развернули)
  prev = 3, current = null

Цикл завершён (current == null)
Ответ: prev (новая голова) = 3

Результат: null ← 1 ← 2 ← 3

Рекурсивная реализация

public ListNode reverseRecursive(ListNode head) {
    // Базовый случай: пустой список или один элемент
    if (head == null || head.next == null) {
        return head;
    }
    
    // Рекурсивно разворачиваем остаток списка
    ListNode newHead = reverseRecursive(head.next);
    
    // Разворачиваем связь между текущим и следующим узлом
    head.next.next = head;  // следующий узел теперь указывает на текущий
    head.next = null;        // текущий узел больше не указывает вперёд
    
    return newHead;  // возвращаем новую голову (неизменна в рекурсии)
}

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

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

Вызов 1: reverseRecursive(1)
  1.next = 2, не null → рекурсия
  
  Вызов 2: reverseRecursive(2)
    2.next = 3, не null → рекурсия
    
    Вызов 3: reverseRecursive(3)
      3.next = null → базовый случай
      return 3 (новая голова)
    
    newHead = 3
    3.next = 2 (развернули)
    2.next = null
    return 3
  
  newHead = 3
  2.next = 1 (развернули)
  1.next = null
  return 3

Итог: 3 → 2 → 1 → null

Альтернатива с явной новой головой

public ListNode reverseRecursiveWithHelper(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode newHead = head;
    reverseHelper(head);
    return newHead;
}

private ListNode reverseHelper(ListNode node) {
    if (node.next == null) {
        return node;  // последний узел - новая голова
    }
    
    ListNode nextNode = node.next;
    ListNode newHead = reverseHelper(nextNode);
    
    // Разворачиваем связь
    nextNode.next = node;
    node.next = null;
    
    return newHead;
}

Тесты

public class ReverseLinkedListTest {
    private ReverseLinkedList solution = new ReverseLinkedList();
    
    @Test
    public void testIterative() {
        ListNode head = createList(new int[]{1, 2, 3, 4, 5});
        ListNode reversed = solution.reverse(head);
        assertListEquals(new int[]{5, 4, 3, 2, 1}, reversed);
    }
    
    @Test
    public void testRecursive() {
        ListNode head = createList(new int[]{1, 2, 3, 4, 5});
        ListNode reversed = solution.reverseRecursive(head);
        assertListEquals(new int[]{5, 4, 3, 2, 1}, reversed);
    }
    
    @Test
    public void testSingleElement() {
        ListNode head = createList(new int[]{1});
        ListNode reversed = solution.reverse(head);
        assertListEquals(new int[]{1}, reversed);
    }
    
    @Test
    public void testTwoElements() {
        ListNode head = createList(new int[]{1, 2});
        ListNode reversed = solution.reverse(head);
        assertListEquals(new int[]{2, 1}, reversed);
    }
    
    @Test
    public void testEmpty() {
        ListNode reversed = solution.reverse(null);
        assertNull(reversed);
    }
    
    @Test
    public void testLargeList() {
        int[] data = new int[1000];
        for (int i = 0; i < 1000; i++) {
            data[i] = i + 1;
        }
        ListNode head = createList(data);
        ListNode reversed = solution.reverse(head);
        
        // Проверяем первый и последний элементы
        assertEquals(1000, reversed.val);
        assertEquals(1, getLastNode(reversed).val);
    }
    
    private void assertListEquals(int[] expected, ListNode actual) {
        ListNode current = actual;
        for (int value : expected) {
            assertNotNull(current);
            assertEquals(value, current.val);
            current = current.next;
        }
        assertNull(current);  // конец списка
    }
    
    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;
    }
    
    private ListNode getLastNode(ListNode head) {
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }
}

Развёртывание части списка

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null || left == right) {
        return head;
    }
    
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode beforeReverse = dummy;
    
    // Идём до позиции left
    for (int i = 0; i < left - 1; i++) {
        beforeReverse = beforeReverse.next;
    }
    
    // Разворачиваем между left и right
    ListNode prev = beforeReverse;
    ListNode current = beforeReverse.next;
    
    for (int i = 0; i < right - left; i++) {
        ListNode next = current.next;
        current.next = prev.next;
        prev.next = next;
        current = next;
    }
    
    return dummy.next;
}

Сравнение подходов

Сложность

Вывод

Итеративный подход — это стандартное решение для промышленного кода. Он использует три указателя (prev, current, next) и один проход по списку. Рекурсивная версия более элегантна, но может привести к переполнению стека на больших списках. На интервью обычно ожидают итеративного решения с чётким объяснением логики.