Skip to main content

Reverse a Doubly Linked List

In this page, we will solve the problem of reversing a doubly linked list.

Problem Description​

Given a doubly linked list of n elements. Your task is to reverse the doubly linked list in-place.

Examples​

Example 1:

Input:
LinkedList: 3 <--> 4 <--> 5
Output: 5 4 3

Example 2:

Input:
LinkedList: 75 <--> 122 <--> 59 <--> 196
Output: 196 59 122 75

Constraints​

  • 1≤1 \leq number of nodes ≤104\leq10^4
  • 0≤0 \leq value of nodes ≤104\leq 10^4

Solution​

Intuition and Approach​

This problem can be solved by iterating over the doubly linked list and interchanging the prev and the next pointer and then return the last node

Approach: Inorder Traversal​

  1. Base Case: we first checks if the head of the list is None, which means the list is empty and so we returns None.
  2. Base Case: we then checks if the head.next is None, which means there is only one node in the list. If so, it returns the head itself, as reversing a single node doesn't change anything.
  3. we next initializes two pointers: curr which is set to head, and prev which is set to None. curr will be used to traverse the list, and prev will eventually point to the new head of the reversed list.
  4. Then we run a while loop until curr becomes None, meaning it has traversed the entire list. Inside the loop:
    • prev is updated to curr, keeping track of the last processed node.
    • then current node's next and prev pointers are swapped to reverse the direction of the list.
    • curr is then moved to the original prev node, which is now curr.next after the swap.
  5. Once the loop finishes, prev will be pointing to the new head of the reversed list and so we returned prev.

Code in Python​

class Solution:
  def reverseDLL(self, head):
    if head==None:return None
    if head.next==None:
        return head
    curr=head
    prev=None
    while curr!=None:
        prev=curr
        curr.next,curr.prev=curr.prev,curr.next
        curr=curr.prev
    return prev

Complexity Analysis​

  • Time Complexity: O(N)O(N)
  • Space Complexity: O(1)O(1)