3294. Convert Doubly Linked List to Array II 🔒

MediumArrayLinked ListDoubly-Linked List

Problem Description

You are given an arbitrary node from a doubly linked list. Each node in this list has a next pointer to the next node and a previous pointer to the previous node. The task is to return an integer array containing the elements of the linked list in their natural order, starting from the head node and proceeding to the end of the list.

Intuition

To solve this problem, the key is understanding the structure of a doubly linked list. Each node has a prev pointer that allows us to traverse backwards and a next pointer for traversing forwards. Since we are given an arbitrary node and not necessarily the head, our first step is to find the head of the list by moving backwards using the prev pointers until we reach a node whose prev is None.

Once we have located the head node, we can start building the result array. By traversing the list from the head using the next pointers, we collect each node's value and append it to our answer array. This approach ensures we gather all values in the correct sequential order. Finally, we return the populated array as our solution.

Learn more about Linked List patterns.

Solution Approach

The solution involves traversing the doubly linked list to both locate the head and collect the values from each node in order. Here's a step-by-step breakdown of the approach:

Finding the Head Node:
- Starting from the given arbitrary node, we traverse backwards using the prev pointers. We continue this process until we reach a node where node.prev is None. This node is identified as the head of the linked list.
- This ensures that regardless of the starting position in the list, we always begin collecting values from the very beginning of the list.
Collecting Values from Nodes:
- With the head node now identified, initialize an empty array ans to store the values.
- Traverse the list starting from the head node, using next pointers. For each node encountered, append the node's value, node.val, to the ans array.
- Continue this traversal until a node whose next is None is encountered, signifying the end of the list.
Returning the Result:
- After completing the traversal and collecting all node values in order, return the filled ans array as the final output.

This approach efficiently retrieves the ordered values of the linked list regardless of the initial node, utilizing the bidirectional nature of the prev and next pointers inherent to a doubly linked list.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach for traversing a doubly linked list.

Consider the doubly linked list with the following nodes and values:

Node A: val = 1
Node B: val = 2
Node C: val = 3
Node D: val = 4

Connections between nodes:

Node A's next points to Node B.
Node B's prev points to Node A and next points to Node C.
Node C's prev points to Node B and next points to Node D.
Node D's prev points to Node C.

Assume you're given an arbitrary node, for example, Node C:

Finding the Head Node:
- Start from Node C.
- Since Node C has a prev pointing to Node B, move to Node B.
- Now at Node B, continue moving to Node A, which is Node B's prev.
- Node A has prev as None, indicating that Node A is the head.
Collecting Values from Nodes:
- With Node A identified as the head, initialize an empty array ans.
- Begin traversing from Node A:
  - Append 1 from Node A to ans.
  - Move to next, reaching Node B, append 2 to ans.
  - Continue to Node C, append 3 to ans.
  - Finally, move to Node D, append 4 to ans.
Returning the Result:
- At this point, ans = [1, 2, 3, 4].
- Since Node D's next is None, indicate the end of traversal.
- Return ans, resulting in the array [1, 2, 3, 4], representing the natural order of the linked list.

This example demonstrates starting from any arbitrary node and retrieving the full list order by leveraging the bidirectional pointers present in a doubly linked list.

Solution Implementation

1from typing import List, Optional
2
3# Definition for a Node in a doubly linked list
4class Node:
5    def __init__(self, val: int, prev: 'Optional[Node]' = None, next: 'Optional[Node]' = None):
6        self.val = val           # The value of the node
7        self.prev = prev         # Reference to the previous node in the list
8        self.next = next         # Reference to the next node in the list
9
10class Solution:
11    def toArray(self, node: 'Optional[Node]') -> List[int]:
12        # Navigate to the head of the list
13        while node and node.prev:
14            node = node.prev
15      
16        # Initialize an empty list to store the values
17        ans = []
18      
19        # Traverse the list and append each node's value to the list
20        while node:
21            ans.append(node.val)
22            node = node.next
23      
24        # Return the list of values
25        return ans
26

1import java.util.ArrayList;
2
3/*
4// Definition for a Node.
5class Node {
6    public int val;    // Value of the node
7    public Node prev;  // Pointer to the previous node
8    public Node next;  // Pointer to the next node
9}
10*/
11
12class Solution {
13    public int[] toArray(Node node) {
14        // Navigate to the head of the doubly linked list
15        while (node != null && node.prev != null) {
16            node = node.prev;
17        }
18      
19        // Create a list to store the values of the nodes
20        ArrayList<Integer> result = new ArrayList<>();
21      
22        // Traverse from the head to the end of the list
23        while (node != null) {
24            // Add the current node's value to the list
25            result.add(node.val);
26            // Move to the next node
27            node = node.next;
28        }
29      
30        // Convert the ArrayList of Integers to an array of int
31        return result.stream().mapToInt(i -> i).toArray();
32    }
33}
34

1#include <vector>
2using namespace std;
3
4// Definition for a doubly-linked list node.
5class Node {
6public:
7    int val;            // Value of the current node
8    Node* prev;         // Pointer to the previous node
9    Node* next;         // Pointer to the next node
10
11    // Default constructor, initializes with 0 and nullptr for prev and next
12    Node() : val(0), prev(nullptr), next(nullptr) {}
13
14    // Constructor: initializes with provided value, sets prev and next to nullptr
15    Node(int x) : val(x), prev(nullptr), next(nullptr) {}
16
17    // Constructor: initializes with provided value and pointers to prev and next nodes
18    Node(int x, Node* prev, Node* next) : val(x), prev(prev), next(next) {}
19};
20
21class Solution {
22public:
23    vector<int> toArray(Node* node) {
24        // Move to the head of the list if not already at the head
25        while (node && node->prev) {
26            node = node->prev;
27        }
28
29        vector<int> ans; // Vector to store the list values in order
30
31        // Traverse the list from head to tail
32        for (; node; node = node->next) {
33            ans.push_back(node->val); // Add current node value to the vector
34        }
35
36        return ans; // Return the vector containing all node values
37    }
38};
39

1// Define the `_Node` interface for representing each node in a doubly linked list.
2interface _Node {
3    val: number;       // The value of the node
4    prev: _Node | null; // Reference to the previous node
5    next: _Node | null; // Reference to the next node
6}
7
8// Converts a linked list starting from a given node into an array of numbers.
9function toArray(node: _Node | null): number[] {
10    // Navigate to the head of the list by moving to the first node: repeat while node is not null and node.prev is not null.
11    while (node && node.prev) {
12        node = node.prev;
13    }
14
15    const result: number[] = []; // Initialize an empty array to hold the node values.
16
17    // Iterate through the list, starting from the head, and collect values into the result array.
18    for (; node; node = node.next) {
19        result.push(node.val);
20    }
21  
22    // Return the array containing all node values from the doubly linked list.
23    return result;
24}
25

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the linked list. The algorithm first traverses to the head of the list and then iterates through each node exactly once, appending each node's value to an array.

Ignoring the space consumption of the answer array which stores the values of all nodes, the space complexity is O(1). This accounts for the usage of other variables in the algorithm, as the storage for the output is not considered part of the algorithm's space complexity in this context.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don’t know