Problem

Given the head of a doubly linked list, reverse the linked list in place. After reversing, the head should point to the last node of the original list, and all next and prev pointers should be adjusted accordingly.

Examples:

Example 1:

---
title: Input
---
 
 graph LR
   A1[1] <--> B2[2] <--> C3[3] <--> D4[4] <--> E5[5]
  
---
title: Output
---
 
 graph LR
   E5[5] <--> D4[4] <--> C3[3] <--> B2[2] <--> A1[1]
  
1
2

Input: head = 1 <-> 2 <-> 3 <-> 4 <-> 5
Output: 5 <-> 4 <-> 3 <-> 2 <-> 1

Example 2:

1
2

Input: head = 1
Output: 1

Solution

Method 1 - Iteration

  1. Traversal and Swapping:
    • Traverse through the doubly linked list.
    • For each node, swap its next and prev pointers.
    • Move to the previous node (prev pointer, which acts as next node after swapping).
  2. Updating Head:
    • At the end of the traversal, update the head to the last node encountered which effectively becomes the new head of the reversed list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Node {
    int val;
    Node prev;
    Node next;
    Node(int x) {
        val = x;
    }
}

public class Solution {
    public Node reverse(Node head) {
        if (head == null)
            return null;

        Node current = head;
        Node newHead = null;

        while (current != null) {
            Node prev = current.prev;
            current.prev = current.next;
            current.next = prev;

            newHead = current;
            current = current.prev;
        }

        return newHead;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Node:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


class Solution:
    def reverse(self, head: "Node") -> "Node":
        if not head:
            return None

        current = head
        new_head = None

        while current:
            # Swap prev and next
            current.prev, current.next = current.next, current.prev

            new_head = current
            current = (
                current.prev
            )  # Move to the previous node, which is the next node after swapping

        return new_head

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the doubly linked list. Each node is processed once.
  • 🧺 Space complexity: O(1), as we use only a constant amount of space for pointers.