3263. Convert Doubly Linked List to Array I 🔒

Problem Description

You are given the head of a doubly linked list, which contains nodes with a next pointer and a previous pointer. Your task is to return an integer array containing the elements of the linked list in order.

Intuition

The problem requires extracting the values from a doubly linked list into a straightforward integer array. The solution involves a simple traversal of the linked list. Since the list is doubly linked, each node has pointers to both the next and the previous nodes. However, the task simplifies because we only need to follow the next pointers starting from the head node. By iterating through the list using the next pointer, we can accumulate the values into an array.

We accomplish this by starting with the head node, checking if it exists, and then continuously moving to the next node, appending each node's value to the array until we reach the end, where the next pointer is None.

Learn more about Linked List patterns.

Solution Approach

The solution focuses on a straightforward approach of "Direct Traversal" to transform the doubly linked list into an integer array. Here's a step-by-step breakdown of the solution:

Initialize an Empty Array:
- Start by creating an empty list ans that will hold the values of the nodes as they are extracted from the doubly linked list.
Traverse the Linked List:
- Begin from the head node of the linked list, referred to as root in the code.
- Use a while loop to iterate through the linked list. The loop continues as long as the current node, root, is not None.
Append Node Values:
- Inside the loop, append the value of the current node to the result array ans using ans.append(root.val).
Move to the Next Node:
- Update the current node to the next node using root = root.next. This takes advantage of the next pointer in the doubly linked list to traverse the list sequentially.
Return the Array:
- Once the loop terminates, indicating that all nodes have been processed, return the array ans as the final result containing all the elements of the linked list in order.

The overall pattern used here is a simple iterative traversal which efficiently solves the problem within a single pass over the linked list, ensuring an O(n) time complexity where n is the number of nodes in the 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 consider a simple example of a doubly linked list containing three nodes with values 1, 2, and 3, arranged in that order. The structure is as follows:

Node 1: val = 1, next points to Node 2, prev is None
Node 2: val = 2, next points to Node 3, prev points to Node 1
Node 3: val = 3, next is None, prev points to Node 2

Using the solution approach outlined earlier, we will transform this doubly linked list into an integer array [1, 2, 3].

Initialize an Empty Array:
- Start with an empty list ans. At this point, ans = [].
Traverse the Linked List:
- Begin at the head, which is Node 1. Set root = head.
Append Node Values:
- In the first iteration, root points to Node 1. Append root.val (which is 1) to ans. Now, ans = [1].
Move to the Next Node:
- Update root to point to the next node, Node 2. Thus, root = root.next.
Continue the Process:
- In the second iteration, root points to Node 2. Append root.val (which is 2) to ans. Now, ans = [1, 2].
- Move root to the next node, Node 3. root = root.next.
Final Node Processing:
- In the third iteration, root points to Node 3. Append root.val (which is 3) to ans. Now, ans = [1, 2, 3].
- Move root to the next node, which is None since Node 3 is the last node.
Return the Array:
- Since root is now None, exit the loop and return ans which is [1, 2, 3].

Through the walk-through of this example, we verified that our approach gathers all node values in the linked list into an array correctly and efficiently, maintaining their order.

Solution Implementation

1from typing import Optional, List
2
3# Definition for a doubly linked list node.
4class Node:
5    def __init__(self, val: int, prev: 'Optional[Node]' = None, next: 'Optional[Node]' = None):
6        self.val = val       # The value held by 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, root: "Optional[Node]") -> List[int]:
12        """Converts a doubly linked list to a list of integers."""
13
14        result = []  # Initialize an empty list to store node values
15
16        # Traverse the doubly linked list starting from the root node
17        while root:
18            result.append(root.val)  # Append current node's value to the result list
19            root = root.next         # Move to the next node in the list
20
21        return result  # Return the list of node values
22

1/*
2// Definition for a Node.
3class Node {
4    public int val;  // Value of the node
5    public Node prev; // Previous node in the linked list
6    public Node next; // Next node in the linked list
7};
8*/
9
10import java.util.ArrayList;
11import java.util.List;
12
13class Solution {
14    public int[] toArray(Node head) {
15        List<Integer> resultList = new ArrayList<>(); // Initialize a list to store node values
16
17        // Traverse the linked list starting from the head
18        while (head != null) {
19            resultList.add(head.val); // Add the current node's value to the list
20            head = head.next; // Move to the next node in the list
21        }
22
23        // Convert the list of integers to an array of int and return
24        return resultList.stream().mapToInt(i -> i).toArray();
25    }
26}
27

1#include <vector>
2using namespace std;
3
4// Definition for a doubly-linked list node.
5class Node {
6public:
7    int val;            // Value of the node
8    Node* prev;         // Pointer to the previous node
9    Node* next;         // Pointer to the next node
10
11    // Constructor to initialize node with a default value of 0 and null pointers
12    Node() : val(0), next(nullptr), prev(nullptr) {}
13  
14    // Constructor to initialize node with a given value and null pointers
15    Node(int x) : val(x), next(nullptr), prev(nullptr) {}
16
17    // Constructor to initialize node with a given value, previous node, and next node
18    Node(int x, Node *prev, Node *next) : val(x), next(next), prev(prev) {}
19};
20
21class Solution {
22public:
23    // Function to convert a doubly-linked list to a vector of integers
24    vector<int> toArray(Node* head) {
25        vector<int> ans; // Initialize an empty vector to store values of nodes
26        for (; head; head = head->next) { // Iterate through each node in the list
27            ans.push_back(head->val); // Append the value of the current node to the vector
28        }
29        return ans; // Return the filled vector
30    }
31};
32

1// Definition for a doubly linked list node
2type Node = {
3  val: number;
4  prev: Node | null;
5  next: Node | null;
6};
7
8// Converts a doubly linked list to an array of values
9function toArray(head: Node | null): number[] {
10  // Initialize an empty array to store node values
11  const ans: number[] = [];
12
13  // Traverse the linked list
14  while (head !== null) {
15    // Add the current node's value to the array
16    ans.push(head.val);
17    // Move to the next node in the list
18    head = head.next;
19  }
20
21  // Return the filled array
22  return ans;
23}
24

Time and Space Complexity

The time complexity of the toArray function is O(n), where n is the number of nodes in the linked list. This is because the function iterates through each node exactly once, appending its value to the list.

The space complexity, ignoring the space consumed by the output list ans, is O(1). This is due to the use of a constant amount of additional space regardless of the input size.

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

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don’t know