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

1. Введение

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

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

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

После того, как мы реверсируем связанный список, заголовок будет указывать на последний элемент исходного связанного списка, а указатель каждого элемента будет указывать на предыдущий элемент исходного связанного списка:

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

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

public class ListNode {

    private int data;
    private ListNode next;

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

   // standard getters and setters
}

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

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

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

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;
}

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

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

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;
}

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

В конце концов, текущий указатель будет нулевым, а предыдущий указатель будет последним элементом старого связанного списка. Таким образом, 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:

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;
}

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

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

@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();
    }
}

5. Вывод

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