Reverse a doubly linked list

Write a program to Reverse the given doubly linked list

Example

Algorithm

Time Complexity : O(n)

Step 1 : create a function which takes a linked list which should be reversed as argument.

Step 2 : Just swap the next and previous of the double linked list
a)    Create a dummy variable node (t) for swap.
b)    t = next of current node
c)    next of current node equal to previous of current node.
d)    previous node equal to t
e)    swap done. If you see the example it will be clear.

Step 3 : call the function on the given Linked list.

Step 4 : print the Linked list, it prints the reversed linked list.

Algorithm Working

C++ Program

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

struct DLL{
	int data;
	DLL *next;
	DLL *prev;
};

void insertAtBeginning(struct DLL **head, int X)
{
	struct DLL * curr = new DLL;
	curr->data = X;
	curr->prev = NULL;
	curr->next = *head;
	if(*head != NULL)
	(*head)->prev = curr;
	*head = curr;
	
}

void reverseDList(struct DLL **head)
{
	struct DLL * temp = *head , *t;
	
	while(temp != NULL)
	{
		t = temp->next;
		temp->next = temp->prev;
		temp->prev = t;
		
		if(temp->prev == NULL) //means last node, so it will become the new head
			*head = temp;
			
		temp = temp->prev;
	}
	
}

void display(struct DLL**head)
{
	struct DLL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	struct DLL *head = NULL;
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"Current list is :- \n";
	display(&head);
	
	reverseDList(&head);
	
	cout<<"\nAfter reversing the doubly linked list it became :- \n";
	display(&head);
	
}
Try It


Next > < Prev
Scroll to Top