Отменить связанный список

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

Отменить связанный список

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

Double LinkedList хранит два адреса. Адрес для предыдущего элемента и следующего элемента.

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

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

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

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

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

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

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 

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

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

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

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 в рекурсивном вызове, чтобы перейти в конец LinkedList. Как только мы достигаем конца, мы устанавливаем предпоследний элемент как следующий за последним элементом и устанавливаем следующий указатель предпоследнего элемента в NULL. Последний элемент будет помечен как новая головка. Используйте следующий код, чтобы изменить связанный список, используя рекурсивный подход.

myLinkedList.head = recursiveReverse(myLinkedList.head);

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

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

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

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