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.

Examples

Example 1:

1
2

Input: head = [1,2,3,4,5], node = 5
Output: [1,2,3,4,5]

Example 2:

1
2

Input: head = [4,5,6,7,8], node = 8
Output: [4,5,6,7,8]

Constraints:

  • The number of nodes in the given list is in the range [1, 500].
  • 1 <= Node.val <= 1000
  • All nodes have unique Node.val.

Solution

Method 1 – Two-Pointer Traversal 1

Intuition

Given an arbitrary node in a doubly linked list, we can always reach the head by following the prev pointers. Once at the head, we can traverse the list in order using the next pointers to collect all values.

Approach

  1. Start from the given node.
  2. Move backward using prev pointers until reaching the head (where prev is null).
  3. From the head, traverse forward using next pointers, collecting each node’s value into an array.
  4. Return the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> toArray(Node* node) {
        Node* head = node;
        while (head->prev) head = head->prev;
        vector<int> ans;
        while (head) {
            ans.push_back(head->val);
            head = head->next;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func toArray(node *Node) []int {
    head := node
    for head.Prev != nil {
        head = head.Prev
    }
    ans := []int{}
    for head != nil {
        ans = append(ans, head.Val)
        head = head.Next
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public List<Integer> toArray(Node node) {
        Node head = node;
        while (head.prev != null) head = head.prev;
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.val);
            head = head.next;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun toArray(node: Node?): List<Int> {
        var head = node
        while (head?.prev != null) head = head.prev
        val ans = mutableListOf<Int>()
        while (head != null) {
            ans.add(head.`val`)
            head = head.next
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def toArray(self, node: 'Optional[Node]') -> list[int]:
        head = node
        while head and head.prev:
            head = head.prev
        ans: list[int] = []
        while head:
            ans.append(head.val)
            head = head.next
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn to_array(mut node: Option<Box<Node>>) -> Vec<i32> {
        let mut head = node.as_ref();
        while let Some(n) = head {
            if n.prev.is_some() {
                head = n.prev.as_ref();
            } else {
                break;
            }
        }
        let mut ans = Vec::new();
        let mut cur = head;
        while let Some(n) = cur {
            ans.push(n.val);
            cur = n.next.as_ref();
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    toArray(node: Node | null): number[] {
        let head = node;
        while (head && head.prev) head = head.prev;
        const ans: number[] = [];
        while (head) {
            ans.push(head.val);
            head = head.next;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the list, as we may traverse the whole list twice (once backward, once forward).
  • 🧺 Space complexity: O(n), for storing the result array.