Reverse a Doubly Linked List in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has two links: one to the next node and one to the previous node. This allows traversal in both directions.

beginner

What does reversing a doubly linked list mean?

Reversing a doubly linked list means changing the direction of the links so that the last node becomes the first, and the first node becomes the last, effectively flipping the list.

intermediate

In reversing a doubly linked list, what happens to the 'next' and 'prev' pointers of each node?

For each node, the 'next' pointer is swapped with the 'prev' pointer. This reverses the direction of the list.

intermediate

Why do we need to update the head pointer after reversing a doubly linked list?

Because the original head becomes the tail after reversal, we must update the head pointer to point to the new first node (which was the original tail).

beginner

What is the time complexity of reversing a doubly linked list?

The time complexity is O(n), where n is the number of nodes, because each node is visited once to swap its pointers.

What pointers are swapped in each node when reversing a doubly linked list?

A Next and Prev pointers

B Next and Head pointers

C Prev and Tail pointers

D Head and Tail pointers

Reversing swaps the 'next' and 'prev' pointers of each node to reverse the list direction.

After reversing a doubly linked list, what should the head pointer point to?

A Original head node

B Middle node

C Null

D Original tail node

The head pointer must point to the original tail node, which becomes the new head after reversal.

What is the time complexity of reversing a doubly linked list with n nodes?

A O(1)

B O(n)

C O(n^2)

D O(log n)

Reversing requires visiting each node once, so the time complexity is O(n).

Which of the following is NOT true about a doubly linked list?

A It only has a pointer to the next node

B Each node has a pointer to the previous node

C It can be traversed in both directions

D Each node has a pointer to the next node

A doubly linked list has pointers to both next and previous nodes, not just next.

What happens to the 'prev' pointer of the new head node after reversal?

A It points to the old head

B It points to the next node

C It points to null

D It points to itself

The new head's 'prev' pointer should be null because it has no previous node.

Explain step-by-step how to reverse a doubly linked list.

Think about what happens to each node's pointers and the head.

Describe why reversing a doubly linked list is easier than reversing a singly linked list.

Consider the extra pointer each node has.