Talentd
FleetCode
Make and follow sheets.Sign in

Convert Doubly Linked List to Array II solution and explanation

MediumArrayDoubly-Linked ListLinked List3 min read83.3% acceptanceUpdated 24 Mar 2026Premium elsewhere, free here
3294 Convert Doubly Linked List to Array II | dubly linked listCode-Yao · 5:28 · 61 viewsWatch on YouTube
10 more videos on this problem
  1. 3294 Convert Doubly Linked List to Array II | dubly linked listCode-Yao · 5:28 · 61 views
  2. CONVERT BINARY SEARCH TREE TO SORTED DOUBLY LINKED LIST | LEETCODE # 426 | PYTHON SOLUTIONCracking FAANG · 18:21 · 24K views
  3. CONVERT BINARY SEARCH TREE TO SORTED DOUBLY LINKED LIST (Leetcode) - Code & Whiteboardbabybear4812 · 14:49 · 6K views
  4. Leetcode - Flatten a Multilevel Doubly Linked List (Python)Timothy H Chang · 8:13 · 5K views
  5. leetcode - Convert Binary Search Tree to Sorted Doubly Linked ListBob Wei · 10:28 · 419 views
  6. Convert Binary Search Tree to Sorted Doubly Linked List || Leetcode 426constantinirimia · 11:29 · 408 views
  7. Leetcode 426 | Binary Search Tree to Doubly Linked ListRed Black Tech · 9:36 · 285 views
  8. leetcode 3263: convert doubly linked list to array : python solutionleetcode blind 75 · 2:00 · 267 views
  9. 426. Convert Binary Search Tree to Sorted Doubly Linked List (Leetcode Medium)Programming Live with Larry · 18:24 · 250 views
  10. Flatten a Multilevel Doubly Linked List - Leet CodeLarry Chiem · 14:41 · 15 views
  11. #LeetCode 3263 | Convert Doubly Linked List to Array I #JavaSleepy Cracker · 1:45 · 5 views

The problem

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:

  • The number of nodes in the given list is in the range [1, 500].
  • 1 <= Node.val <= 1000
  • All nodes have unique Node.val.

Approach overview

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.

Solution

We can start from the given node and traverse the linked list backward until we reach the head node. Then, we traverse the linked list forward from the head node, adding the values of the nodes we encounter to the answer array.

After the traversal is complete, return the answer array.

The time complexity is O(n), where n is the number of nodes in the linked list. Ignoring the space consumption of the answer array, the space complexity is O(1).

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next
"""


class Solution:
    def toArray(self, node: "Optional[Node]") -> List[int]:
        while node.prev:
            node = node.prev
        ans = []
        while node:
            ans.append(node.val)
            node = node.next
        return ans
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
};
*/

class Solution {
    public int[] toArray(Node node) {
        while (node != null && node.prev != null) {
            node = node.prev;
        }
        var ans = new ArrayList<Integer>();
        for (; node != null; node = node.next) {
            ans.add(node.val);
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }
}
/**
 * Definition for doubly-linked list.
 * class Node {
 *     int val;
 *     Node* prev;
 *     Node* next;
 *     Node() : val(0), next(nullptr), prev(nullptr) {}
 *     Node(int x) : val(x), next(nullptr), prev(nullptr) {}
 *     Node(int x, Node *prev, Node *next) : val(x), next(next), prev(prev) {}
 * };
 */
class Solution {
public:
    vector<int> toArray(Node* node) {
        while (node && node->prev) {
            node = node->prev;
        }
        vector<int> ans;
        for (; node; node = node->next) {
            ans.push_back(node->val);
        }
        return ans;
    }
};
/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     prev: _Node | null
 *     next: _Node | null
 *
 *     constructor(val?: number, prev? : _Node, next? : _Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.prev = (prev===undefined ? null : prev);
 *         this.next = (next===undefined ? null : next);
 *     }
 * }
 */

function toArray(node: _Node | null): number[] {
    while (node && node.prev) {
        node = node.prev;
    }
    const ans: number[] = [];
    for (; node; node = node.next) {
        ans.push(node.val);
    }
    return ans;
}
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Prev *Node
 * }
 */

func toArray(node *Node) (ans []int) {
	for node != nil && node.Prev != nil {
		node = node.Prev
	}
	for ; node != nil; node = node.Next {
		ans = append(ans, node.Val)
	}
	return
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Single-Pass Linked List TraversalO(n)O(n)General case. Fastest and simplest way to convert a linked list into an array.
Two-Pass Traversal with Preallocated ArrayO(n)O(n)Useful when avoiding dynamic array resizing or when exact memory allocation is preferred.

Frequently asked questions

Is Convert Doubly Linked List to Array II easy or hard?

Convert Doubly Linked List to Array II is generally considered a medium-level problem. The logic is straightforward traversal, but the question checks understanding of linked list structure and careful pointer iteration.

Convert Doubly Linked List to Array II Python/Java solution

In both Python and Java, iterate through the linked list starting from head and append each node value to a list or array structure. Python typically uses a list with append operations, while Java uses an ArrayList before converting to an array if needed.

How to solve Convert Doubly Linked List to Array II in O(n)?

Iterate through the list starting from the head node. At each step append the current node's value to an array and move to current.next. Stop when the pointer becomes null. This linear traversal ensures O(n) time with a single pass over the nodes.

What is the best approach for Convert Doubly Linked List to Array II?

The best approach is a single-pass traversal of the doubly linked list. Start from the head and follow the next pointer while pushing each node value into an array. This runs in O(n) time and uses O(n) space for the resulting array.

Is Convert Doubly Linked List to Array II asked at Google/Amazon/Meta?

Linked list traversal and structure conversion problems commonly appear in interviews at companies like Amazon, Google, and Meta. Variants of converting linked structures into arrays test understanding of pointer traversal and basic data structure manipulation.

What data structure is used in Convert Doubly Linked List to Array II?

The problem uses a doubly linked list as input and converts it into an array. The traversal relies on the next pointer of each node, while the result is stored sequentially in a dynamic array or list structure.

What is the time complexity of Convert Doubly Linked List to Array II?

The optimal solution runs in O(n) time where n is the number of nodes in the doubly linked list. Each node is visited exactly once during traversal. Space complexity is O(n) because the output array stores all node values.

Comments

Now write it yourselfClose this page and solve Convert Doubly Linked List to Array II in the editor, without looking.
Practise Convert Doubly Linked List to Array II