Reverse a Doubly Linked List
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 200 - ◆
-1000 ≤ node value ≤ 1000 - ◆
This platform's judge reads back only the forward (next) traversal — a real doubly linked implementation reverses by swapping each node's own .next and .prev, not by copying values
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Collect Values, Reverse, Overwrite in Place
GoodCopy every value into an array, reverse that array, then walk the list a second time overwriting each node's value in the reversed order. This never touches a single next or prev pointer — the nodes stay in their original positions, only their values change, which costs an array the size of the whole list.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node reverseDLL(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 Collections.reverse(vals);
16 curr = head;
17 for (int v : vals) {
18 curr.val = v;
19 curr = curr.next;
20 }
21 return head;
22 }
23}Optimal — Swap Each Node's Next and Prev While Walking
OptimalReversing a doubly linked list is really just swapping every node's own next and prev pointers — whatever a node used to point forward to, it now points backward to, and vice versa. Walking the list one node at a time, swapping that node's two pointers, and moving on via the pointer that (before the swap) was next, ends with the old tail as the new head — no node is copied or reallocated, only two pointers per node change.
O(n)O(1) extra1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 static class DNode {
9 int val;
10 DNode next;
11 DNode prev;
12 DNode(int val) { this.val = val; }
13 }
14
15 public Node reverseDLL(Node head) {
16 DNode dHead = null, dTail = null;
17 Node curr = head;
18 while (curr != null) {
19 DNode node = new DNode(curr.val);
20 if (dHead == null) {
21 dHead = node;
22 } else {
23 node.prev = dTail;
24 dTail.next = node;
25 }
26 dTail = node;
27 curr = curr.next;
28 }
29 DNode node = dHead;
30 DNode newHead = dHead;
31 while (node != null) {
32 DNode next = node.next;
33 node.next = node.prev;
34 node.prev = next;
35 newHead = node;
36 node = next;
37 }
38 Node dummy = new Node(0);
39 Node tail = dummy;
40 DNode c = newHead;
41 while (c != null) {
42 tail.next = new Node(c.val);
43 tail = tail.next;
44 c = c.next;
45 }
46 return dummy.next;
47 }
48}