LeetCode 3294 - Convert Doubly Linked List to Array II

LeetCode Problem 3294

Difficulty: 🟡 Medium
Topics: Array, Linked List, Doubly-Linked List

Solution

Problem Understanding

This problem gives us a pointer to an arbitrary node inside a doubly linked list. Unlike many linked list problems, we are not guaranteed to receive the head of the list. Instead, we may receive any node somewhere in the middle or even the tail.

A doubly linked list node contains three fields:

• val, the integer stored in the node
• next, a pointer to the next node
• prev, a pointer to the previous node

Our task is to return all node values in the correct list order as an integer array.

For example, suppose the list is:

1 <-> 2 <-> 3 <-> 4 <-> 5

If we are given the node containing 5, we still need to return:

[1, 2, 3, 4, 5]

This means we cannot simply traverse forward from the given node. We must first locate the true head of the linked list by following prev pointers backward.

The constraints are small, with at most 500 nodes, which means even less optimized approaches would work comfortably within limits. However, the goal is still to design the cleanest and most efficient solution possible.

The problem also guarantees:

• The list contains at least one node
• All node values are unique
• The structure is a valid doubly linked list
• The input node always belongs to the list

Several edge cases are important:

• The given node may already be the head
• The given node may be the tail
• The list may contain only one node
• Traversing backward incorrectly could miss the head
• Traversing forward before locating the head would produce an incomplete array

Because the list is doubly linked, we can move in both directions, which is the key observation that makes the solution straightforward.

Approaches

Brute Force Approach

A brute force style solution would first collect all nodes reachable from the given node in both directions separately.

One possible implementation is:

1. Traverse backward using prev pointers and store values in a temporary list.
2. Reverse that temporary list because values were collected backward.
3. Traverse forward from the original node using next pointers.
4. Combine the results carefully while avoiding duplication of the starting node.

This approach works because every node in the list is reachable from the given node through either prev or next links.

However, the implementation becomes unnecessarily complicated. We must manage two traversals, handle reversing, and avoid duplicate inclusion of the starting node. The extra bookkeeping makes the solution harder to reason about.

Optimal Approach

The better solution uses the structure of a doubly linked list more naturally.

The key insight is that every node has access to its predecessor through the prev pointer. Therefore, starting from the given node, we can repeatedly move backward until we reach the true head, which is the node whose prev pointer is None or nil.

Once we have the head, the problem becomes a standard linked list traversal:

1. Start from the head
2. Traverse using next
3. Append each value to the answer array

This approach is clean, simple, and optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Requires backward collection, reversal, and duplicate handling
Optimal	O(n)	O(1), excluding output	First locate head, then perform normal forward traversal

Algorithm Walkthrough

1. Start with the given node.

The input node may be anywhere in the list, so we cannot immediately begin building the output array. 2. Move backward until the head is reached.

While the current node has a non-null prev pointer, move to current.prev.

After this loop finishes, the current node is guaranteed to be the head because no further previous node exists. 3. Initialize an empty result array.

This array will store the linked list values in order. 4. Traverse forward from the head.

While the current node is not null:

• Append current.val to the result array
• Move to current.next

5. Return the result array.

Since we started at the true head and traversed forward exactly once, the values are collected in correct order.

Why it works

The correctness comes from two properties of doubly linked lists.

First, every node can reach the head by repeatedly following prev pointers. Since the list is finite and properly connected, this process eventually reaches the unique node whose prev pointer is null.

Second, traversing forward from the head using next pointers visits every node exactly once in correct order. Therefore, the produced array exactly matches the linked list sequence.

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, node: 'Optional[Node]') -> List[int]:
        # Move backward to find the head
        while node.prev:
            node = node.prev

        result = []

        # Traverse forward and collect values
        while node:
            result.append(node.val)
            node = node.next

        return result

The implementation begins by locating the true head of the doubly linked list. This is done with a simple loop that repeatedly follows the prev pointer until no previous node exists.

Once the head is found, we initialize an empty result list. We then perform a standard linked list traversal using the next pointer.

At each node, we append the node's value to the output array. Because traversal starts from the head and proceeds forward, values are collected in the exact order required by the problem.

The implementation is concise because the doubly linked structure already provides all navigation capability we need.

Go Solution

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

func toArray(head *Node) []int {
    // Move backward to find the real head
    for head.Prev != nil {
        head = head.Prev
    }

    result := []int{}

    // Traverse forward and collect values
    for head != nil {
        result = append(result, head.Val)
        head = head.Next
    }

    return result
}

The Go implementation follows exactly the same logic as the Python solution.

One important Go-specific detail is the use of nil instead of Python's None. The traversal loops terminate when pointers become nil.

The result is stored in a slice, which dynamically grows as values are appended. Since the maximum list size is only 500 nodes, repeated appends are perfectly efficient for this problem.

Also note that the original problem statement contains a typo in the function signature:

func toArray(head *node) []int

The correct type name should be *Node, matching the struct definition.

Worked Examples

Example 1

Input:

head = [1,2,3,4,5]
node = 5

The given node is the tail.

Initial structure:

1 <-> 2 <-> 3 <-> 4 <-> 5
                               ^
                             node

Step 1, Move backward to find head

Current Node	prev exists?	Action
5	Yes	Move to 4
4	Yes	Move to 3
3	Yes	Move to 2
2	Yes	Move to 1
1	No	Stop

Now we are at the head node.

Step 2, Traverse forward

Current Node	Result Array
1	[1]
2	[1, 2]
3	[1, 2, 3]
4	[1, 2, 3, 4]
5	[1, 2, 3, 4, 5]

Final output:

[1,2,3,4,5]

Example 2

Input:

head = [4,5,6,7,8]
node = 8

Initial structure:

4 <-> 5 <-> 6 <-> 7 <-> 8
                               ^
                             node

Step 1, Move backward

Current Node	prev exists?	Action
8	Yes	Move to 7
7	Yes	Move to 6
6	Yes	Move to 5
5	Yes	Move to 4
4	No	Stop

Step 2, Traverse forward

Current Node	Result Array
4	[4]
5	[4, 5]
6	[4, 5, 6]
7	[4, 5, 6, 7]
8	[4, 5, 6, 7, 8]

Final output:

[4,5,6,7,8]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited at most once while moving backward and once while moving forward
Space	O(1), excluding output	Only a few pointer variables are used

The algorithm is linear because every node participates in at most two traversals. One traversal moves backward to locate the head, and the second traversal moves forward to build the answer.

The auxiliary space usage is constant because no additional data structures proportional to input size are allocated. The returned array itself is not counted as extra space since it is required output.

Test Cases

from typing import Optional, List

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

        result = []

        while node:
            result.append(node.val)
            node = node.next

        return result

def build_dll(values):
    nodes = [Node(v) for v in values]

    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
        nodes[i + 1].prev = nodes[i]

    return nodes

sol = Solution()

# Example 1, given node is tail
nodes = build_dll([1, 2, 3, 4, 5])
assert sol.toArray(nodes[-1]) == [1, 2, 3, 4, 5]

# Example 2, another tail input
nodes = build_dll([4, 5, 6, 7, 8])
assert sol.toArray(nodes[-1]) == [4, 5, 6, 7, 8]

# Single node list
nodes = build_dll([10])
assert sol.toArray(nodes[0]) == [10]

# Given node is already head
nodes = build_dll([1, 2, 3])
assert sol.toArray(nodes[0]) == [1, 2, 3]

# Given node is middle node
nodes = build_dll([5, 10, 15, 20, 25])
assert sol.toArray(nodes[2]) == [5, 10, 15, 20, 25]

# Two node list, start from second node
nodes = build_dll([7, 8])
assert sol.toArray(nodes[1]) == [7, 8]

# Larger list
values = list(range(1, 101))
nodes = build_dll(values)
assert sol.toArray(nodes[50]) == values

Test	Why
Tail node input	Verifies backward traversal works correctly
Second example	Confirms general correctness on another list
Single node list	Validates smallest possible input
Node already at head	Ensures unnecessary backward traversal is avoided correctly
Middle node input	Tests arbitrary node access
Two node list	Validates minimal multi-node structure
Large list	Confirms scalability and traversal correctness

Edge Cases

Single Node List

The smallest valid input contains only one node. In this case, both prev and next are null.

A buggy implementation might assume at least one backward or forward move is possible. Our solution handles this naturally because both loops terminate immediately, and the single value is returned correctly.

Given Node Is Already the Head

If the provided node is already the first node, the backward traversal should stop immediately.

An incorrect implementation could accidentally move past the head or mishandle null pointers. Our condition:

while node.prev:

ensures movement only happens when a previous node exists.

Given Node Is the Tail

This is one of the most important scenarios because traversing only forward would produce an incomplete result containing just the tail node.

Our algorithm explicitly solves this by first locating the true head before collecting values. Even if the input node is the final node in the list, backward traversal reconstructs access to the entire structure.

Given Node Is in the Middle

The input node may be anywhere inside the linked list.

This case tests whether the implementation correctly combines backward discovery with forward traversal. By first locating the head and then restarting traversal from there, the solution guarantees the full list is returned regardless of the starting position.