Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Given a bidirectional list, the task is to reverse the given bidirectional list.

For example, see the figure below.

(a) Original bidirectional linked lists

(b) Reverse bidirectional linked lists

This is an easy way to reverse a bidirectional list. All we need to do is swap the prev and next Pointers for all nodes, change the preV for the header (or start), and change the last header pointer.

#include <bits/stdc++.h>
using namespace std;

class Node
{
	public:
	int data;
	Node *next;
	Node *prev;
};

void reverse(Node **head_ref)
{
	Node *temp = NULL;
	Node *current = *head_ref;
	while(current ! =NULL)
	{
		temp = current->prev;
		current->prev = current->next;
		current->next = temp;			
		current = current->prev;
	}
	if(temp ! =NULL )
		*head_ref = temp->prev;
}

void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; prev is alwaysNULL */
	new_node->prev = NULL;
	new_node->next = (*head_ref);	
	if((*head_ref) ! =NULL)
	(*head_ref)->prev = new_node ;
	(*head_ref) = new_node;
}

void printList(Node *node)
{
	while(node ! =NULL)
	{
		cout << node->data << ""; node = node->next; }}int main(a)
{
	/* Start with the empty list */
	Node* head = NULL;
	
	push(&head, 2);
	push(&head, 4);
	push(&head, 8);
	push(&head, 10);
	
	cout << "Raw linked list" << endl;
	printList(head);

	reverse(&head);
	
	cout << "\n Reverse linked list" << endl;
	printList(head);		
	
	return 0;
}
Copy the code

Output:

The original list10 8 4 2Reverse a linked list2 4 8 10
Copy the code

Time complexity: O(N), where N represents the number of nodes in the bidirectional linked list. Secondary space: O(1) We can also reverse bidirectional linked lists by swapping data instead of Pointers. The methods used to reverse arrays can be used to exchange data. If the size of the data item is larger, the cost of exchanging data can be higher compared to Pointers. If you find any of the above code/algorithms incorrect, please comment or find a better way to solve the same problem.

Method 2:

The same problem can be solved by using a stack.

Steps:

  1. Continue pushing the node’s data onto the stack. -> O(n)
  2. Constantly pop up elements and update the bidirectional linked list
#include <bits/stdc++.h>
using namespace std;
struct LinkedList {
	struct Node {
		int data;
		Node *next, *prev;
		Node(int d)
		{
			data = d;
			next = prev = NULL; }}; Node* head =NULL;
	void reverse(a)
	{
		stack<int> st;
		Node* temp = head;
		while(temp ! =NULL) {
			st.push(temp->data);
			temp = temp->next;
		}
		temp = head;
		while(temp ! =NULL) {
			temp->data = st.top(a); st.pop();
			temp = temp->next;
		}
	}

	void Push(int new_data)
	{
		Node* new_node = new Node(new_data);
		new_node->prev = NULL;
		new_node->next = head;
		if(head ! =NULL) {
			head->prev = new_node;
		}
		head = new_node;
	}
	void printList(Node* node)
	{
		while (node) {
			cout << node->data << ""; node = node->next; }}};int main(a)
{
	LinkedList list;
	list.Push(2);
	list.Push(4);
	list.Push(8);
	list.Push(10);
	cout << "Raw linked list" << endl;
	list.printList(list.head);
	list.reverse(a); cout << endl; cout <<"The reverse linked list is" << endl;
	list.printList(list.head);
}
Copy the code

The output

The original list10 8 4 2The reverse linked list is2 4 8 10
Copy the code

Time complexity: O(N) Auxiliary space: O(N)

In this approach, we iterate through the list once and add elements to the stack, then iterate through the entire list again to update all elements. The whole thing takes 2n, which is order n time.