LeetCode Solutions Blog

Convert Doubly Linked List to Array II

Number: 3615

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an arbitrary node from a doubly linked list, return an integer array containing the elements of the list in order. Since the node is arbitrary and may not be the head, you first need to traverse backwards to find the head of the list, then iterate forward to build the resulting array.

Key Insights

The input node can be any node in the doubly linked list, not necessarily the head.
Use the previous pointer to backtrack to the head of the list.
Use the next pointer from the head to traverse the entire list and build the array.
The solution involves two passes over part or all of the list but overall remains linear in time complexity.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the list. Space Complexity: O(n), as we're storing each node's value in the output array.

Solution

The solution begins by finding the head of the doubly linked list by following the "prev" pointers until a node with no previous node is reached. This gives the starting node of the list. Once the head is located, we traverse the list using the "next" pointers, appending each node’s value to an array. The final array is then returned. This approach ensures that the elements are returned in the order of the list, from head to tail.

Code Solutions

# Define the Node structure for clarity. In an actual solution, the Node class is usually provided.
class Node:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val     # Node's value
        self.prev = prev   # Pointer to the previous node
        self.next = next   # Pointer to the next node

def convertDoublyLinkedListToArray(node):
    # Step 1: Find the head by traversing backwards using the prev pointer
    while node.prev:
        node = node.prev
    head = node
    
    # Step 2: Traverse forward from the head to create the array of values
    result = []
    while node:
        result.append(node.val)  # Append the current node's value to the result list
        node = node.next         # Move to the next node in the list
    return result

# Example usage:
# Create a doubly linked list: 1 <-> 2 <-> 3 <-> 4 <-> 5, and choose node with value 5 as the arbitrary input.
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n1.next = n2
n2.prev = n1
n2.next = n3
n3.prev = n2
n3.next = n4
n4.prev = n3
n4.next = n5
n5.prev = n4

# n5 is the arbitrary node.
print(convertDoublyLinkedListToArray(n5))  # Expected output: [1, 2, 3, 4, 5]