Watch 10 video solutions for Convert Doubly Linked List to Array II, a medium level problem involving Array, Linked List, Doubly-Linked List. This walkthrough by NeetCode has 99,168 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an arbitrary node from a doubly linked list, which contains nodes that have a next pointer and a previous pointer.
Return an integer array which contains the elements of the linked list in order.
Example 1:
Input: head = [1,2,3,4,5], node = 5
Output: [1,2,3,4,5]
Example 2:
Input: head = [4,5,6,7,8], node = 8
Output: [4,5,6,7,8]
Constraints:
[1, 500].1 <= Node.val <= 1000Node.val.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single-Pass Linked List Traversal | O(n) | O(n) | General case. Fastest and simplest way to convert a linked list into an array. |
| Two-Pass Traversal with Preallocated Array | O(n) | O(n) | Useful when avoiding dynamic array resizing or when exact memory allocation is preferred. |