Convert Doubly Linked List to Array II - Solution & Explanation

Problem Overview: You are given the head of a doubly linked list and need to return an array containing the node values in order. The list must be traversed node by node using the next pointers while collecting values into a dynamic array structure.

Approach 1: Traverse the Linked List (O(n) time, O(n) space)

Start at the head node and iterate through the list using the next pointer until you reach null. For each node visited, append its value to an output array. This works because a doubly linked list already stores nodes in sequential order, so a single pass naturally preserves ordering. The algorithm performs one linear scan over the list, making it optimal for this problem. This approach is the most common technique when converting structures from a linked list into an array.

Approach 2: Two-Pass Traversal with Preallocation (O(n) time, O(n) space)

First iterate through the list to count the total number of nodes. Use this count to initialize an array of the exact required size. Then run a second traversal from the head and place each node value into the array using an index pointer. The logic remains simple but avoids repeated dynamic resizing in languages where array growth may cause reallocation. This pattern is useful when working with memory-sensitive environments or strict performance constraints. It still relies on sequential traversal of a doubly linked list.

Recommended for interviews: The single-pass traversal approach is what interviewers expect. It demonstrates that you understand how to iterate through linked structures efficiently. Mentioning the two-pass preallocation variant shows awareness of memory allocation behavior, but the straightforward O(n) traversal is usually sufficient.