Problem Description

You are given a random node from a doubly linked list. A doubly linked list is a data structure where each node has:

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

The challenge is that you're not given the head of the list - you're given some arbitrary node that could be anywhere in the list (beginning, middle, or end).

Your task is to return an array containing all the values from the linked list in their original order, from the first node to the last node.

For example, if the doubly linked list is 1 <-> 2 <-> 3 <-> 4 <-> 5 and you're given the node with value 3, you need to:

1. Find your way back to the head of the list (node with value 1)
2. Traverse forward through the entire list
3. Return [1, 2, 3, 4, 5]

The solution works by first traversing backward using the prev pointers until reaching the head (where prev is None), then traversing forward using the next pointers to collect all values in order.

Intuition

Since we're given an arbitrary node in a doubly linked list and need to return all values in order, the key insight is that we need to find the starting point first.

Think of it like being dropped in the middle of a train - you don't know which car you're in, but you need to list all the cars from the engine to the caboose. What would you do? You'd walk backward through the cars until you reach the engine (the first car), then walk forward through the entire train to list them all.

The same logic applies here. A doubly linked list gives us the ability to move in both directions using prev and next pointers. So our strategy becomes:

1. Find the head: Keep moving backward using node.prev until we reach a node where prev is None. This is the head of the list.

2. Collect all values: Once at the head, traverse forward using node.next and collect each node's value into an array.

The beauty of this approach is its simplicity - we don't need to worry about where we started or keep track of visited nodes. We just need to:

• Go all the way back to the beginning
• Then go all the way forward to the end

This guarantees we'll capture every node exactly once and in the correct order. The time complexity is O(n) where n is the total number of nodes, and we only need O(1) extra space (not counting the output array).

Learn more about Linked List patterns.

Solution Approach

The implementation follows a two-phase approach: finding the head and then collecting all values.

Phase 1: Finding the Head

while node.prev:
    node = node.prev

Starting from the given node, we traverse backward using the prev pointer. The loop continues as long as node.prev exists (is not None). When the loop terminates, node points to the head of the linked list - the node that has no previous node.

Phase 2: Collecting Values

ans = []
while node:
    ans.append(node.val)
    node = node.next
return ans

Once we've found the head, we initialize an empty list ans to store our result. We then traverse the entire linked list from head to tail:

• Append the current node's value to ans
• Move to the next node using node = node.next
• Continue until node becomes None (we've passed the last node)

The algorithm handles all edge cases naturally:

• If the given node is already the head, the first while loop doesn't execute
• If the given node is the tail, we still traverse back to the head first
• Single-node lists work correctly since we start and end at the same node

Time and Space Complexity:

• Time: O(n) where n is the total number of nodes. In the worst case, we traverse the entire list twice - once backward to find the head, once forward to collect values.
• Space: O(1) extra space for the traversal (not counting the output array which is O(n) and required for the result).

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given: A doubly linked list 10 <-> 20 <-> 30 <-> 40 <-> 50 where we're given the node containing value 30.

Step-by-Step Execution:

Phase 1: Finding the Head

Starting position: We're at node 30

• Current node: 30, node.prev exists (points to 20) → Move to 20
• Current node: 20, node.prev exists (points to 10) → Move to 10
• Current node: 10, node.prev is None → Stop! We've found the head

Phase 2: Collecting Values

Starting from the head node 10:

• Initialize ans = []
• Current node: 10 → Append 10 to ans, move to next → ans = [10]
• Current node: 20 → Append 20 to ans, move to next → ans = [10, 20]
• Current node: 30 → Append 30 to ans, move to next → ans = [10, 20, 30]
• Current node: 40 → Append 40 to ans, move to next → ans = [10, 20, 30, 40]
• Current node: 50 → Append 50 to ans, move to next → ans = [10, 20, 30, 40, 50]
• Current node: None → Stop traversal

Result: Return [10, 20, 30, 40, 50]

This example demonstrates how the algorithm correctly handles being given a middle node. The same logic works regardless of which node we start from - we always find our way back to the head first, then collect all values in order.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the doubly linked list. This is because:

• The first while loop traverses backwards from the given node to find the head of the list, which takes at most O(n) operations
• The second while loop traverses forward through all nodes from head to tail, which takes exactly O(n) operations
• In total, we visit each node at most twice, resulting in O(n) + O(n) = O(2n) = O(n) time complexity

The space complexity is O(1) if we exclude the space used by the answer array ans. The algorithm only uses a constant amount of extra space for the node pointer variable. If we include the answer array, the space complexity would be O(n) since we store all n node values in the list.

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

Common Pitfalls

1. Null Node Handling

One of the most common pitfalls is not properly handling the case when the input node is None. If the function receives a None input, attempting to access node.prev will raise an AttributeError.

Problematic Code:

def toArray(self, node: Optional["Node"]) -> List[int]:
    # This will crash if node is None
    while node.prev:  # AttributeError if node is None
        node = node.prev

Solution:

def toArray(self, node: Optional["Node"]) -> List[int]:
    # Handle None input gracefully
    if not node:
        return []
  
    while node.prev:
        node = node.prev
  
    result = []
    while node:
        result.append(node.val)
        node = node.next
  
    return result

2. Infinite Loop in Corrupted Lists

If the doubly linked list has a cycle in the backward direction (corrupted data structure), the algorithm will get stuck in an infinite loop while searching for the head.

Example of Corrupted List:

Node1 <-> Node2 <-> Node3
  ^                    |
  |____________________|

Solution with Cycle Detection:

def toArray(self, node: Optional["Node"]) -> List[int]:
    if not node:
        return []
  
    # Use a set to detect cycles while finding the head
    visited = set()
    while node.prev and id(node) not in visited:
        visited.add(id(node))
        node = node.prev
  
    # Collect values going forward
    result = []
    visited.clear()
    while node and id(node) not in visited:
        visited.add(id(node))
        result.append(node.val)
        node = node.next
  
    return result

3. Memory Inefficiency with Large Lists

While the basic solution is correct, for very large lists, repeatedly appending to a list can cause multiple memory reallocations. Though Python handles this reasonably well, in performance-critical scenarios, pre-allocating space could be beneficial.

Optimized Approach for Known Size:

def toArray(self, node: Optional["Node"]) -> List[int]:
    if not node:
        return []
  
    # Find head and count nodes simultaneously
    head = node
    count = 1
  
    # Count backward
    while head.prev:
        head = head.prev
        count += 1
  
    # Count forward from original node
    temp = node.next
    while temp:
        temp = temp.next
        count += 1
  
    # Pre-allocate result array
    result = [0] * count
  
    # Fill the array
    i = 0
    while head:
        result[i] = head.val
        head = head.next
        i += 1
  
    return result

The most critical pitfall to avoid is the null node handling, as this will cause immediate runtime errors. The cycle detection is important for defensive programming against corrupted data structures, though properly implemented doubly linked lists shouldn't have cycles.