Reverse a Doubly Linked List in DSA Javascript - Execution Trace

Concept Flow - Reverse a Doubly Linked List

Start at head node

↓

Swap node.prev and node.next

↓

Move to node.prev (old next)

↓

Repeat until node is null

↓

Update head to last processed node

↓

Done

We start at the head, swap each node's previous and next pointers, move forward using the old next pointer, and finally update the head to the last node processed.

Execution Sample

DSA Javascript

function reverseDoublyLinkedList(head) {
  let current = head;
  let temp = null;
  while (current) {
    temp = current.prev;
    current.prev = current.next;
    current.next = temp;
    current = current.prev;
  }
  if (temp) head = temp.prev;
  return head;
}

This code reverses a doubly linked list by swapping prev and next pointers of each node and updating the head.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node 1	None	1 <-> 2 <-> 3 <-> 4 <-> null
2	Swap prev and next of Node 1	Node 1	prev: null -> Node 2, next: Node 2 -> null	1 <- 2 <-> 3 <-> 4 <-> null
3	Move current to old next (current.prev)	Node 2	current: Node 1 -> Node 2	1 <- 2 <-> 3 <-> 4 <-> null
4	Swap prev and next of Node 2	Node 2	prev: Node 1 -> Node 3, next: Node 3 -> Node 1	1 <- 2 <- 3 <-> 4 <-> null
5	Move current to old next (current.prev)	Node 3	current: Node 2 -> Node 3	1 <- 2 <- 3 <-> 4 <-> null
6	Swap prev and next of Node 3	Node 3	prev: Node 2 -> Node 4, next: Node 4 -> Node 2	1 <- 2 <- 3 <- 4 <-> null
7	Move current to old next (current.prev)	Node 4	current: Node 3 -> Node 4	1 <- 2 <- 3 <- 4 <-> null
8	Swap prev and next of Node 4	Node 4	prev: Node 3 -> null, next: null -> Node 3	1 <- 2 <- 3 <- 4
9	Move current to old next (current.prev)	null	current: Node 4 -> null	1 <- 2 <- 3 <- 4
10	Update head to last processed node	Node 4	head: Node 1 -> Node 4	4 <-> 3 <-> 2 <-> 1 <-> null

💡 current becomes null, loop ends, head updated to last processed node

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
current	Node 1	Node 2	Node 3	Node 4	null	null
temp	null	null	Node 1	Node 2	Node 3	Node 3
head	Node 1	Node 1	Node 1	Node 1	Node 1	Node 4

Key Moments - 3 Insights

Why do we move current to current.prev after swapping?

After swapping prev and next, current.prev points to the original next node. So moving current to current.prev moves forward in the original list. See execution_table steps 3, 5, 7, 9.

Why do we update head to temp.prev at the end?

temp holds the previous node before current became null. After the last swap, temp.prev points to the new head. This is shown in execution_table step 10.

What happens to the original next pointer after swapping?

It becomes the prev pointer after swapping. This is why we use current.prev to move forward. See pointer changes in steps 2, 4, 6, 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 5?

A Node 4

B Node 2

C Node 3

D Node 1

💡 Hint

Check the 'Current Node' column at step 5 in execution_table.

At which step does the current pointer become null?

A Step 8

B Step 9

C Step 10

D Step 7

💡 Hint

Look at the 'Current Node' column to find when it changes to null.

If we forget to update the head at the end, what would be the head node?

A Node 1

B null

C Node 4

D Node 2

💡 Hint

See variable_tracker 'head' value before final update.

Concept Snapshot

Reverse a Doubly Linked List:
- Start at head node
- For each node, swap prev and next pointers
- Move current to old next (current.prev after swap)
- Repeat until current is null
- Update head to last processed node
- Result: list reversed with head at original tail

Full Transcript

To reverse a doubly linked list, we begin at the head node. For each node, we swap its prev and next pointers. Because of this swap, the original next node is now accessible via current.prev, so we move current to current.prev to continue traversal. We repeat this until current becomes null, meaning we have processed all nodes. Finally, we update the head pointer to the last node processed, which is the new head of the reversed list. This process reverses the direction of the list, so the tail becomes the new head and vice versa.

Practice

1. What does reversing a doubly linked list mean?

easy

A. Adding a new node at the end

B. Deleting all nodes from the list

C. Sorting the nodes in ascending order

D. Swapping the next and previous pointers of each node

Solution

1. Step 1: Understand doubly linked list structure

   Each node has two pointers: one to the next node and one to the previous node.

2. Step 2: Reverse means swapping pointers

   Reversing means changing each node's next pointer to previous and previous pointer to next.

3. Final Answer:

   Swapping the next and previous pointers of each node -> Option D

4. Quick Check:

   Reverse = swap next and prev pointers [OK]

Hint: Reverse means swap next and prev pointers [OK]

Common Mistakes:

• Thinking reverse means deleting nodes
• Confusing reverse with sorting
• Adding nodes instead of reversing pointers

2. Which of the following is the correct way to swap the next and prev pointers of a node in JavaScript?

easy

A. node.prev = node.next; node.next = node.prev;

B. node.next = node.prev; node.prev = node.next;

C. let temp = node.next; node.next = node.prev; node.prev = temp;

D. node.next = node.next; node.prev = node.prev;

Solution

1. Step 1: Use a temporary variable to hold one pointer

   Store node.next in temp to avoid losing its value.

2. Step 2: Swap pointers correctly

   Assign node.next = node.prev, then node.prev = temp to complete swap.

3. Final Answer:

   let temp = node.next; node.next = node.prev; node.prev = temp; -> Option C

4. Quick Check:

   Swap with temp variable = correct [OK]

Hint: Use temp variable to swap pointers safely [OK]

Common Mistakes:

• Swapping without temp loses pointer data
• Assigning both pointers to same value
• Not swapping pointers at all

3. What will be the output list after reversing this doubly linked list?

Head -> 1 <-> 2 <-> 3 <-> null

After reversal, what is the new head node's value?

medium

A. 3

B. 1

C. 2

D. null

Solution

1. Step 1: Original list order

   List is 1 <-> 2 <-> 3, head points to 1.

2. Step 2: Reverse swaps pointers, so last node becomes head

   After reversal, 3 becomes the new head, pointing backward to 2 and forward to null.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   New head after reverse = last node = 3 [OK]

Hint: New head after reverse is original tail [OK]

Common Mistakes:

• Assuming head stays same after reverse
• Confusing node values order
• Thinking null becomes head

4. Identify the bug in this reverse function for a doubly linked list:

function reverse(head) {
  let current = head;
  while (current != null) {
    let temp = current.next;
    current.next = current.prev;
    current.prev = temp;
    current = current.next;
  }
  return head;
}

medium

A. The function does not update the head to the new first node

B. Swapping next and prev pointers is done incorrectly

C. The loop condition should be current.next != null

D. The function should return null instead of head

Solution

1. Step 1: Check pointer swapping

   Swapping next and prev pointers is done correctly using temp variable.

2. Step 2: Check head update after reversal

   Function returns original head, but after reversal head should be last node visited, so head is not updated.

3. Final Answer:

   The function does not update the head to the new first node -> Option A

4. Quick Check:

   Head must update to new first node [OK]

Hint: Update head to last processed node after loop [OK]

Common Mistakes:

• Not updating head after reversal
• Incorrect loop condition causing infinite loop
• Returning wrong node at end

5. Given a doubly linked list with nodes:

Head -> 10 <-> 20 <-> 30 <-> 40 <-> null

After reversing the list, what is the correct sequence of nodes starting from the new head?

hard

A. 10 <-> 20 <-> 30 <-> 40 <-> null

B. 40 <-> 30 <-> 20 <-> 10 <-> null

C. 40 <-> 20 <-> 30 <-> 10 <-> null

D. null <-> 40 <-> 30 <-> 20 <-> 10

Solution

1. Step 1: Original list order

   Nodes are linked as 10 <-> 20 <-> 30 <-> 40, head at 10.

2. Step 2: Reverse swaps pointers and changes head to last node

   After reversal, head is 40, and nodes link backward as 40 <-> 30 <-> 20 <-> 10.

3. Final Answer:

   40 <-> 30 <-> 20 <-> 10 <-> null -> Option B

4. Quick Check:

   Reverse list order = original tail to head [OK]

Hint: Reversed list order is original list backwards [OK]

Common Mistakes:

• Not reversing the order correctly
• Mixing node values in wrong order
• Confusing null placement in list