Convert Doubly Linked List to Array I - Video Solutions
leetcode 3263: convert doubly linked list to array : python solution
Convert Doubly Linked List to Array I - Video Solution
Watch 3 video solutions for Convert Doubly Linked List to Array I, a easy level problem involving Array, Linked List, Doubly-Linked List. This walkthrough by leetcode blind 75 has 301 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given the head of 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,3,2,1]
Output: [1,2,3,4,3,2,1]
Example 2:
Input: head = [2,2,2,2,2]
Output: [2,2,2,2,2]
Example 3:
Input: head = [3,2,3,2,3,2]
Output: [3,2,3,2,3,2]
Constraints:
- The number of nodes in the given list is in the range
[1, 50]. 1 <= Node.val <= 50
Approach Overview
Problem Overview: Given the head of a doubly linked list, the task is to return an array containing the node values in the same order as they appear in the list. You start from the head node and follow the next pointers until the end, copying each value into an array.
Approach 1: Direct Traversal (O(n) time, O(n) space)
The most straightforward solution is to iterate through the doubly linked list starting from the head. At each node, append the node's value to a dynamic array (such as a Python list or Java ArrayList). Continue moving through the list using the next pointer until you reach null. This works because a doubly linked list preserves element order through its sequential node connections. The traversal touches every node exactly once, giving O(n) time complexity where n is the number of nodes. The array stores all values, so the extra space used is O(n). This approach is simple, readable, and the most common implementation in interviews.
Approach 2: Two-Pass Traversal with Preallocated Array (O(n) time, O(n) space)
Another option is to first walk through the list to count the number of nodes. Once you know the size, allocate an array of that exact length. Then perform a second traversal and fill the array sequentially with node values. This avoids dynamic resizing that some array implementations perform during repeated appends. The trade-off is an additional pass through the linked list. Time complexity remains O(n) since each node is visited twice, and space complexity stays O(n) for the resulting array.
Recommended for interviews: Direct traversal is the expected answer. Interviewers want to see that you understand how to iterate through a linked structure using pointers and convert it into a contiguous array representation. Mentioning the two-pass preallocation variant shows deeper awareness of memory behavior in dynamic arrays, but the single-pass append approach is typically preferred for its clarity and minimal code.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Traversal | O(n) | O(n) | Best general solution. Simple single pass through the list while appending values to an array. |
| Two-Pass Traversal with Preallocation | O(n) | O(n) | Useful when you want to allocate the exact array size before filling it. |