Reverse a Doubly Linked List

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Swap prev and next pointers for every node. The old tail becomes the new head.

Algorithm

1Traverse: for each node, swap node.prev and node.next.
2Return the last node visited as new head.

Common Pitfalls

•Swap pointers, do not reassign values. The last processed node (old tail) is the new head.

Reverse a Doubly Linked List.java

Java

// Approach: Swap prev and next pointers for every node while traversing.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;
    Node prev;

    Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class Solution {
    public Node reverse(Node head) {
        Node current = head;
        Node temp = null;

        while (current != null) {
            // Swap next and prev
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;

            // Move to next node in original list (which is prev after swap)
            current = current.prev;
        }

        // Fix head to point to the new front
        if (temp != null)
            head = temp.prev;

        return head;
    }
}

Was this solution helpful?