Problem

You are given any node of a doubly linked list — not necessarily the head. Each node has fields val, prev and next. Return an array containing all values of the list in forward order (head to tail).

Input / Output

• Input: a reference to one node somewhere in the list.
• Output: integer array of all values from head to tail.

Examples

Example 1 Input: list 1 <-> 2 <-> 3 <-> 4 <-> 5, given node is the one with value 3 Output: [1, 2, 3, 4, 5]

Example 2 Input: list 7 <-> 9, given node is 9 Output: [7, 9]

Example 3 Input: single node 42 Output: [42]

Constraints

• 1 <= number of nodes <= 10^5

Approach

Two-phase walk (O(1) extra space).

1. From the given node, follow prev pointers until prev is null — that node is the head.
2. From the head, follow next pointers and append every value.

Total steps: at most n backwards plus n forwards.

Alternative without finding the head first. Collect values going backwards from the given node into a temporary list, reverse it, then append the values going forward from node.next. Same complexity but slightly more code; the two-phase version is cleaner.

Complexity

• Time: O(n)
• Space: O(n) for the output; O(1) auxiliary.

Follow-ups

• What if the list is circular (the tail's next points to the head)? You cannot search for a null prev; instead remember the starting node and stop when you return to it — walk backwards to collect the "before" portion, then forwards, using the start node as the sentinel.
• Return values in reverse order (follow next to the tail, then walk prev).
• Detect corruption where a.next.prev != a while traversing.

Reference solution (Python)

def dll_to_array_from_any(node):
    if node is None:
        return []
    while node.prev:
        node = node.prev
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out

Test cases

Input	Expected
list 1<->2<->3<->4<->5, given node 3	[1,2,3,4,5]
list 7<->9, given node 9	[7,9]
single node 42	[42]
given node is head	same as forward traversal