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

Автор оригинала: Gang Wu.

1. введение

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

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

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

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

В 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 и current , чтобы представить два соседних элемента в связанном списке. Для каждой итерации мы меняем местами эти два элемента, а затем переходим к следующим двум элементам.

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

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

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

@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 .