Problem Description

You are given the head of a doubly linked list. A doubly linked list is a data structure where each node contains:

• A value (val)
• A pointer to the next node (next)
• A pointer to the previous node (prev)

Your task is to traverse the linked list starting from the head and return an integer array that contains all the values of the nodes in order from head to tail.

For example, if the doubly linked list is 1 ↔ 2 ↔ 3 ↔ 4, you should return the array [1, 2, 3, 4].

The solution traverses the linked list from the head node, visiting each node sequentially using the next pointer. At each node, the value is added to a result array. The traversal continues until reaching the end of the list (when root becomes None). Finally, the array containing all node values in order is returned.

Intuition

The problem asks us to convert a doubly linked list into an array. The most natural way to think about this is to follow how we would manually read through the list: start at the beginning and visit each node one by one until we reach the end.

Since we need the elements "in order" and we're given the head of the list, we should traverse forward using the next pointers. Even though this is a doubly linked list with prev pointers as well, we don't need to use them for this problem - we can treat it just like a regular singly linked list traversal.

The key insight is that we simply need to:

1. Start at the head node
2. Record the current node's value
3. Move to the next node
4. Repeat until we've visited all nodes

This is a straightforward linear traversal pattern. We collect values as we go, storing them in an array that preserves the order of our traversal. When we can't move forward anymore (when root becomes None), we know we've reached the end of the list and have collected all values.

The simplicity of this approach comes from recognizing that converting a linked structure to an array is fundamentally about visiting each element exactly once in the correct order, which a basic traversal naturally accomplishes.

Learn more about Linked List patterns.

Solution Approach

The solution uses a direct traversal approach to convert the doubly linked list into an array. Here's how the implementation works:

Algorithm Steps:

1. Initialize an empty result array: We create an empty list ans = [] that will store the values from the linked list nodes.

2. Traverse the linked list: We use a while loop with the condition while root: to continue traversing as long as we haven't reached the end of the list (when root becomes None).

3. Collect node values: Inside the loop, we:

   • Append the current node's value to our result array: ans.append(root.val)
   • Move to the next node: root = root.next

4. Return the result: After the traversal completes, we return the ans array containing all node values in order.

Data Structure Used:

• We use a Python list (ans) to store the values, which provides O(1) amortized time for append operations.

Pattern: This is a classic linked list traversal pattern. The code follows the standard template for iterating through a linked list:

while current_node:
    # Process current node
    current_node = current_node.next

Time and Space Complexity:

• Time Complexity: O(n), where n is the number of nodes in the linked list. We visit each node exactly once.
• Space Complexity: O(n) for storing the n values in the result array. The traversal itself only uses O(1) extra space for the pointer.

The beauty of this solution lies in its simplicity - we don't need to use the prev pointers at all, and the forward traversal naturally gives us the elements in the correct order.

Example Walkthrough

Let's walk through the solution with a small doubly linked list: 10 ↔ 20 ↔ 30

Initial State:

• head points to the first node with value 10
• ans = [] (empty result array)
• root = head (our traversal pointer starts at the head)

Step 1: Process first node (value = 10)

• Check: root is not None, so we enter the loop
• Append root.val (10) to ans: ans = [10]
• Move forward: root = root.next (now points to node with value 20)

Step 2: Process second node (value = 20)

• Check: root is not None, so we continue
• Append root.val (20) to ans: ans = [10, 20]
• Move forward: root = root.next (now points to node with value 30)

Step 3: Process third node (value = 30)

• Check: root is not None, so we continue
• Append root.val (30) to ans: ans = [10, 20, 30]
• Move forward: root = root.next (now root = None since this was the last node)

Step 4: Exit loop

• Check: root is None, so we exit the while loop
• Return ans = [10, 20, 30]

The algorithm successfully traversed the entire linked list from head to tail, collecting each value in order. Notice how we only used the next pointers to move forward through the list - the prev pointers weren't needed for this traversal.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list. The algorithm traverses through each node exactly once, visiting all n nodes in the list sequentially. Each operation inside the loop (appending to the list and moving to the next node) takes O(1) time, resulting in a total time complexity of O(n).

Space Complexity: O(1) if we exclude the space used by the output array ans. The algorithm only uses a constant amount of extra space for the pointer variable root that traverses the list. The space consumed by the answer array itself is O(n) since it stores all n values from the linked list, but following the convention stated in the reference answer, this is not counted toward the space complexity as it is required for the output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Input Parameter Name

One common pitfall is accidentally modifying the input parameter name (like using root instead of the original parameter name) and forgetting to update all references, leading to NameError exceptions.

Problematic Code:

def toArray(self, root: Optional['Node']) -> List[int]:
    result = []
    while head:  # Error: 'head' is not defined
        result.append(head.val)
        head = head.next
    return result

Solution: Use consistent naming throughout the function. Either rename the parameter or use a separate variable:

def toArray(self, root: Optional['Node']) -> List[int]:
    result = []
    current = root  # Create a separate traversal pointer
    while current:
        result.append(current.val)
        current = current.next
    return result

2. Not Handling None/Empty List

While the provided solution handles this correctly with while current_node:, beginners might write code that doesn't properly check for an empty list.

Problematic Code:

def toArray(self, root: Optional['Node']) -> List[int]:
    result = [root.val]  # Error if root is None
    current = root.next
    while current:
        result.append(current.val)
        current = current.next
    return result

Solution: Always check if the head is None before accessing its properties.

3. Infinite Loop Due to Circular References

In real-world scenarios, a corrupted doubly linked list might have circular references. The standard traversal would result in an infinite loop.

Solution with Cycle Detection:

def toArray(self, root: Optional['Node']) -> List[int]:
    result = []
    visited = set()
    current = root
  
    while current:
        # Check for cycle
        if id(current) in visited:
            break  # or raise an exception for corrupted list
        visited.add(id(current))
      
        result.append(current.val)
        current = current.next
      
    return result

4. Accidentally Using the Previous Pointer

Since it's a doubly linked list, developers might mistakenly traverse backward or mix up the pointers.

Problematic Code:

def toArray(self, root: Optional['Node']) -> List[int]:
    result = []
    while root:
        result.append(root.val)
        root = root.prev  # Wrong direction!
    return result

Solution: Be explicit about the traversal direction and stick to using next for forward traversal.