Reverse A Doubly Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
158 upvotes
Asked in companies
Dream11WalmartIBM

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
8
1 2 3 4 5 6 7 8
Sample Output 1 :
8 7 6 5 4 3 2 1
Explanation for sample output 1
Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8
Output: 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1
Explanation: It's self explanatory.
Sample Input 2 :
5
5 8 4 9 1
Sample Output 2 :
1 9 4 8 5
Constraints :
1 <= 'N' <= 10^3
0 <= 'data' <= 10^3 

Where 'N' is the size of the doubly linked list.

Time Limit: 1 sec
Hint

We need to swap next and prev pointers between every two consecutive nodes.

Approaches (2)
Recursive

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.
Time Complexity

O(N), where N is the length of the doubly linked list.

 

We are traversing a linked list of size N that takes O(N) time. Hence, the overall Time Complexity is O(N).

Space Complexity

O(N), where N is the length of the doubly linked list.

 

We are making N recursive calls that take O(N) Space Complexity. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Reverse A Doubly Linked List
Full screen
Console