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

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

Переворачивание связного списка

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

Двусвязный связный список хранит два адреса. Адрес для предыдущего элемента и следующего элемента.

Для того чтобы инвертировать односвязный список на месте, нам нужно изменить направление указателей так, чтобы следующий элемент теперь указывал на предыдущий элемент. Вот входные и выходные данные. Голова связного списка – это первый узел. Ни для какого другого элемента не сохранен адрес. Хвост связного списка – последний узел. Следующий адрес, сохраненный в этом узле, равен null. Мы можем инвертировать связанный список так, чтобы голова и хвост также менялись, используя:

• Итеративный подход
• Рекурсивный подход

Итеративный подход для инверсии связанного списка

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

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

• Сохраните следующий узел текущего элемента в указателе на следующий.
• Установите следующий узел текущего узла на предыдущий. Это строка MVP.
• Переместите предыдущий к текущему.
• Переместите текущий элемент к следующему.

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

Вот очень простая реализация связного списка. Обратите внимание, что это не готовая к производству реализация, и мы сделали ее простой, чтобы наше внимание оставалось на алгоритме разворота связного списка.

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

Приведен ниже Java-программа для итеративного разворота связного списка и печати его элементов:

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

Вывод:

1 2 3 
3 2 1 

Рекурсивно перевернуть связанный список

Чтобы рекурсивно перевернуть связанный список, нам нужно разделить его на две части: голову и оставшуюся часть. Голова изначально указывает на первый элемент. Оставшаяся часть указывает на следующий элемент после головы.

Мы рекурсивно проходим по связанному списку до предпоследнего элемента. Как только мы достигли последнего элемента, устанавливаем его в качестве головы. Затем мы делаем следующее, пока не достигнем начала связанного списка. node.next.next = node; node.next = null; Чтобы не потерять связь с исходной головой, мы сохраним копию экземпляра головы.

Ниже приведена иллюстрация вышеописанной процедуры. Программа на Java для рекурсивного переворота связанного списка выглядит следующим образом:

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

Мы просто передаем head.next в рекурсивный вызов, чтобы перейти в конец связанного списка. Как только мы достигаем конца, устанавливаем предпоследний элемент в качестве следующего после последнего элемента и устанавливаем указатель на следующий элемент предпоследнего элемента в NULL. Последний элемент будет отмечен как новая голова. Используйте следующий код для переворота связанного списка с использованием рекурсивного подхода.

myLinkedList.head = recursiveReverse(myLinkedList.head);

Вывод останется таким же, как при предыдущем итеративном подходе.

Пространственно-временная сложность обращения связанного списка

Временная сложность – O(n) Пространственная сложность – O(1)

Вы можете проверить полный код и больше примеров DS & Algorithm нашего репозитория GitHub.