Last Updated: 6 Feb, 2021

Reverse A Doubly Linked List

Easy

Asked in companies

Solve now

Problem statement

You are given a doubly-linked list of size 'N', consisting of positive integers. Now your task is to reverse it and return the head of the modified list.

Note:

A doubly linked list is a kind of linked list that is bidirectional, meaning it can be traversed in both forward and backward directions.

Example:

Input: 
4
4 3 2 1

This means you have been given doubly linked list of size 4 = 4 <-> 3 <-> 2 <-> 1.

Output: 
1 2 3 4

This means after reversing the doubly linked list it becomes 1 <-> 2 <-> 3 <-> 4.

Input format :

The first line contains an integer 'N', the size of the linked list.
The second line contains 'N' space-separated integers.

Output format :

The output contains all the integers of the reversed doubly linked list.

Note :

You don’t need to print anything. Just implement the given function.

Solve now

Approaches

01 Approach

The idea is to use recursion and the given function will iterate the doubly linked list in the previous direction by calling itself recursively to reverse it.

Base condition = If the node is NULL then return NULL.

Recursive calls = Swap the next and prev pointers.

Base condition :
- If HEAD is equal to NULL or HEAD ->NEXT = NULL then do:
  - Return HEAD.
Recursive calls :
- Take a pointer TEMP = SOLVE(HEAD->NEXT) .
- TEMP->PREV = NULL .
- HEAD ->NEXT ->NEXT = HEAD .
- HEAD->PREV = HEAD->NEXT.
- HEAD->NEXT = NULL.
- Return TEMP.

Solve now

02 Approach

The idea is to swap next and prev pointers between every two consecutive nodes. And in last making the last node as head and return it.

Let’s say the head of the given linked list is HEAD.
Initialize a pointer CURR= HEAD, it will be used to iterate over the linked list.
Initialize a pointer TEMP= NULL, it will store a pointer to the previous node of CURR.
Iterate while HEAD is not NULL :
- TEMP = CURR -> PREV.
- CURR->PREV = CURR ->NEXT.
- CURR->NEXT = TEMP.
- CURR = CURR->PREV.
The new head will be TEMP->PREV so :
- HEAD = TEMP->PREV .
Return HEAD.

Solve now