LL 4 - Reverse a Doubly Linked List

Problem

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

Example 1:

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

Example 2:

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

Solution

Optimal Approach

The idea is simple: take one node and swap the previous pointer reference with the next pointer reference.

Here, we take previous node as the left node and next node as the right node, and perform the swapping for each node. We iterate through temp by moving temp to the right node.

We store the temp reference in the ans node because temp will become new head after manipulating the last node. Hence, we return this as our new head.

public static Node reverseDLL(Node  head)
{
    //if head is null or only one node
    if(head==null || head.next==null) return head;

    Node temp = head;
    Node ans = temp;


    Node left = null;
    Node right = null;

    while(temp!=null){
        left = temp.prev;
        right = temp.next;

        temp.next = left;
        temp.prev = right;

        //storing temp before overriding in ans
        ans = temp;
        temp = right;
    }

    return ans;
}

Another version

Here, we don't store the temp value in the ans. Instead, we use left pointer reference. This is because when we swap references for each node, our iteration stops at null, but we have reference to the previous node, which is left pointer.

In the reversed list, the last node will be the head. The left pointer is the second node of the reversed linked list, and hence left.prev gives us the head of the linked list.

public static Node reverseDLL(Node  head){
    //Your code here
    if(head==null || head.next==null) return head;

    Node temp = head;
    Node left = null;
    Node right = null;

    while(temp!=null){
        left = temp.prev;
        right = temp.next;

        temp.next = left;
        temp.prev = right;

        temp = right;
    }

    return left.prev;
}