«Реверс связанного списка в Java»

«1. Введение

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

2. Структура данных связанного списка

Связный список — это линейная структура данных, в которой указатель в каждом элементе определяет порядок. Каждый элемент связанного списка содержит поле данных для хранения данных списка и поле указателя для указания на следующий элемент в последовательности. Кроме того, мы можем использовать указатель head, чтобы указать на начальный элемент связанного списка: указать на предыдущий элемент исходного связанного списка:

В Java у нас есть класс LinkedList для реализации двусвязного списка, реализующего интерфейсы List и Deque. Однако в этом руководстве мы будем использовать общую структуру данных односвязного списка.

Начнем с класса ListNode для представления элемента связанного списка:

Класс ListNode имеет два поля:

public class ListNode {

    private int data;
    private ListNode next;

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }

   // standard getters and setters
}

Целочисленное значение для представления данных элемента Указатель/ссылка на следующий элемент

Связанный список может содержать несколько объектов ListNode. Например, мы можем создать приведенный выше пример связанного списка с циклом:

3. Реализация итеративного алгоритма

ListNode constructLinkedList() {
    ListNode head = null;
    ListNode tail = null;
    for (int i = 1; i <= 5; i++) {
        ListNode node = new ListNode(i);
        if (head == null) {
            head = node;
        } else {
            tail.setNext(node);
        }
        tail = node;
    }
    return head;
}

Давайте реализуем итеративный алгоритм на Java:

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

ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextElement = current.getNext();
        current.setNext(previous);
        previous = current;
        current = nextElement;
    }
    return previous;
}

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

Мы можем проверить эту итеративную реализацию с помощью простого модульного теста:

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

@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
 
    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseList(head);
 
    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

4. Реализация рекурсивного алгоритма

Теперь давайте реализуем рекурсивный алгоритм на Java:

В функции reverseListRecursive мы рекурсивно посещаем каждый элемент в связанном списке, пока не достигнем последнего. Этот последний элемент станет новым заголовком обратно связанного списка. Кроме того, мы добавляем посещенный элемент в конец частично перевернутого связанного списка.

ListNode reverseListRecursive(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.getNext() == null) {
        return head;
    }
    ListNode node = reverseListRecursive(head.getNext());
    head.getNext().setNext(head);
    head.setNext(null);
    return node;
}

Точно так же мы можем проверить эту рекурсивную реализацию с помощью простого модульного теста:

5. Заключение

@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
 
    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseListRecursive(head);
 
    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

В этом руководстве мы реализовали два алгоритма для реверсирования связанного списка. Как всегда, исходный код статьи доступен на GitHub.

«