Convert Doubly Linked List to Array II - Practice Coding Problems

Convert Doubly Linked List to Array II - Problem

You are given an arbitrary node from a doubly linked list, which contains nodes that have a next pointer and a previous pointer. Return an integer array which contains the elements of the linked list in order.

Since you start from an arbitrary node (not necessarily the head), you need to first find the beginning of the list, then traverse from head to tail to collect all values.

Input & Output

Example 1 — Starting from Middle

$ Input: node pointing to value 3 in list [1,2,3,4,5]

› Output: [1,2,3,4,5]

💡 Note: Starting from node with value 3, we move backward to find head (value 1), then traverse forward collecting all values: 1→2→3→4→5

Example 2 — Starting from Head

$ Input: node pointing to value 10 in list [10,20,30]

› Output: [10,20,30]

💡 Note: Starting from head node (value 10), no backward movement needed, just traverse forward: 10→20→30

Example 3 — Single Node

$ Input: node pointing to value 42 in list [42]

› Output: [42]

💡 Note: List has only one node, so it's both head and tail. Result is simply [42]

Constraints

The number of nodes in the list is in the range [1, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
The given node is guaranteed to be part of a doubly linked list

Visualization

Tap to expand

Understanding the Visualization

Input

Given arbitrary node in doubly linked list [1,2,3,4,5]

Process

Find head by going backward, then traverse forward

Output

Return complete array [1,2,3,4,5]

Key Takeaway

🎯 Key Insight: First find the beginning, then collect everything in order

Asked in

M Microsoft 25 a Amazon 20 G Google 15

The key insight is to first find the head of the doubly linked list by moving backward, then traverse forward to collect all values. The optimal approach uses O(n) time with two passes: one to find the head and one to collect values. Space complexity is O(n) for the result array.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass with Size Calculation	O(n)	O(n)	Find head, count nodes, then collect values in one forward pass
Find Head Then Traverse	O(n)	O(n)	Go backward to find head, then forward to collect all values

Single Pass with Size Calculation — Algorithm Steps

Step 1: Find head by moving backward
Step 2: Count total nodes in forward pass
Step 3: Collect all values in final forward pass

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Head

Move backward to find the beginning

Count Nodes

Count total nodes for exact array allocation

Collect Values

Fill pre-allocated array with all values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
    struct ListNode* prev;
};

int* solution(struct ListNode* node, int* returnSize) {
    *returnSize = 0;
    if (!node) return NULL;
    
    // Find the head (leftmost node)
    struct ListNode* head = node;
    while (head->prev) {
        head = head->prev;
    }
    
    // Count total nodes
    int count = 0;
    struct ListNode* current = head;
    while (current) {
        count++;
        current = current->next;
    }
    
    // Allocate result array of exact size
    int* result = (int*)malloc(count * sizeof(int));
    *returnSize = count;
    
    // Traverse from head to collect all values
    current = head;
    int i = 0;
    while (current) {
        result[i] = current->val;
        i++;
        current = current->next;
    }
    
    return result;
}

struct ListNode* buildDoublyLinkedList(int* values, int size) {
    if (size == 0) return NULL;
    
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = values[0];
    head->next = NULL;
    head->prev = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = values[i];
        newNode->next = NULL;
        newNode->prev = current;
        current->next = newNode;
        current = newNode;
    }
    
    return head;
}

struct ListNode* findNodeAtIndex(struct ListNode* head, int index) {
    struct ListNode* current = head;
    for (int i = 0; i < index && current; i++) {
        current = current->next;
    }
    return current;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array input
    int values[1000];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token) {
        values[size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int startIndex = 0;
    if (fgets(line, sizeof(line), stdin)) {
        startIndex = atoi(line);
    }
    
    // Build list and find starting node
    struct ListNode* head = buildDoublyLinkedList(values, size);
    struct ListNode* node = findNodeAtIndex(head, startIndex);
    
    // Call solution and print result
    int returnSize;
    int* result = solution(node, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three passes through the list: find head O(k), count nodes O(n), collect values O(n), total O(n)

✓ Linear Growth

Space Complexity

O(n)

Result array stores exactly n values with no extra space

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass with Size Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler