LeetCode 3263 - Convert Doubly Linked List to Array I

Difficulty: 🟢 Easy
Topics: Array, Linked List, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to convert a doubly linked list into a standard integer array while preserving the order of elements. In a doubly linked list, each node contains a value (val) and two pointers: next (pointing to the next node) and prev (pointing to the previous node). The input is a reference to the head of the doubly linked list, and the output is a Python list or Go slice containing all the node values from the first node to the last.

The constraints indicate that the linked list has at most 50 nodes, and each node value is between 1 and 50. This is a small input size, so even a straightforward traversal is efficient. The problem guarantees at least one node exists, so we do not need to handle a None or nil head for empty lists.

Important edge cases include a list with only one node, a list where all values are the same, and alternating patterns. These are simple but could reveal careless mistakes in traversal or array append logic.

Approaches

The brute-force approach is effectively the only feasible approach given the simplicity of the problem. We can iterate through the linked list from head to tail, collecting values in an array. The key observation is that a doubly linked list allows traversal in both directions, but since we only need the forward order, we can ignore the prev pointers entirely. This makes the problem linear in time with a straightforward solution.

The comparison table for approaches is as follows:

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Traverse the list from head to tail, appending values to an array
Optimal	O(n)	O(n)	Identical to brute-force due to the small size and simplicity; no further optimization possible

Algorithm Walkthrough

Initialize an empty array to store the node values.
Set a pointer current to the head of the linked list.
While current is not None or nil, do the following:
Append the value current.val to the array.
Move current to the next node using current.next.
Once current becomes None or nil, the traversal is complete, and the array contains all node values in order.
Return the array.

Why it works: The algorithm works because it maintains a single pointer that progresses from the first node to the last. At each step, we add the current node's value to the result array, ensuring that all nodes are captured exactly once in their original order.

Python Solution

from typing import List, Optional

"""
# 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, root: 'Optional[Node]') -> List[int]:
        result = []
        current = root
        while current is not None:
            result.append(current.val)
            current = current.next
        return result

The Python implementation initializes an empty list result to hold the values. We then traverse the linked list starting from root, appending each node's value. The loop stops when current becomes None, meaning we have reached the end of the list. Finally, the list is returned.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Prev *Node
 * }
 */

func toArray(head *Node) []int {
    result := []int{}
    current := head
    for current != nil {
        result = append(result, current.Val)
        current = current.Next
    }
    return result
}

In Go, we use a slice result to store the node values. We traverse the linked list with a for loop checking current != nil, appending each Val to the slice, and moving to the next node with current.Next. Go slices handle dynamic resizing automatically, so this is equivalent to Python's list append.

Worked Examples

Example 1: head = [1,2,3,4,3,2,1]

Step	current.val	result
1	1	[1]
2	2	[1,2]
3	3	[1,2,3]
4	4	[1,2,3,4]
5	3	[1,2,3,4,3]
6	2	[1,2,3,4,3,2]
7	1	[1,2,3,4,3,2,1]
8	None	stop

Example 2: head = [2,2,2,2,2] → result [2,2,2,2,2]

Example 3: head = [3,2,3,2,3,2] → result [3,2,3,2,3,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once in a single traversal.
Space	O(n)	The array storing the node values grows linearly with the number of nodes.

The reasoning is straightforward: every node is processed once, and we store each value in a list or slice, which dominates the space usage.

Test Cases

# test cases
from typing import Optional

def build_dll(values: list[int]) -> Optional['Node']:
    if not values:
        return None
    head = Node(values[0])
    current = head
    for val in values[1:]:
        new_node = Node(val)
        current.next = new_node
        new_node.prev = current
        current = new_node
    return head

sol = Solution()

# Provided examples
assert sol.toArray(build_dll([1,2,3,4,3,2,1])) == [1,2,3,4,3,2,1]  # Example 1
assert sol.toArray(build_dll([2,2,2,2,2])) == [2,2,2,2,2]          # Example 2
assert sol.toArray(build_dll([3,2,3,2,3,2])) == [3,2,3,2,3,2]      # Example 3

# Edge cases
assert sol.toArray(build_dll([1])) == [1]                           # Single element
assert sol.toArray(build_dll([50]*50)) == [50]*50                   # Maximum nodes and values
assert sol.toArray(build_dll([1,2])) == [1,2]                       # Two elements

Test	Why
`[1,2,3,4,3,2,1]`	Standard varied input
`[2,2,2,2,2]`	All values identical
`[3,2,3,2,3,2]`	Alternating pattern
`[1]`	Single node edge case
`[50]*50`	Maximum size and value edge case
`[1,2]`	Small size edge case

Edge Cases

Single Node: A linked list with one node could fail if the loop assumes a next node exists. The implementation correctly handles this because the while loop checks current != None.

All Identical Values: Lists where all node values are the same should be preserved in order. Appending each value individually ensures no accidental deduplication occurs.

Maximum Size List: With 50 nodes, we test the upper bound of the constraints. Python lists and Go slices dynamically handle this size, so no overflow or memory issues arise.

Empty List: Although the constraints guarantee at least one node, if an empty list were possible, the current code would return an empty array/slice naturally.