Build a Doubly Linked List from an Array of Values
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of values ≤ 200 - ◆
-1000 ≤ each value ≤ 1000 - ◆
This platform's judge reads back only the forward (next) traversal — the point of the exercise is correctly wiring both links while building, not what the wire format can verify
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Two Passes: Create, Then Link Both Directions
GoodFirst pass: create every node up front, holding no links yet. Second pass: revisit every position and wire both its .next (pointing forward) and its .prev (pointing backward) using neighbors that already exist in the array. Splitting node creation from link-wiring into two full passes keeps the logic simple, at the cost of walking the values twice.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 static class DNode {
9 int val;
10 DNode next;
11 DNode prev;
12 DNode(int val) { this.val = val; }
13 }
14
15 public Node buildDLL(int[] values) {
16 int n = values.length;
17 DNode[] nodes = new DNode[n];
18 for (int i = 0; i < n; i++) {
19 nodes[i] = new DNode(values[i]);
20 }
21 for (int i = 0; i < n; i++) {
22 if (i + 1 < n) nodes[i].next = nodes[i + 1];
23 if (i > 0) nodes[i].prev = nodes[i - 1];
24 }
25 if (n == 0) return null;
26 Node dummy = new Node(0);
27 Node tail = dummy;
28 for (DNode d : nodes) {
29 tail.next = new Node(d.val);
30 tail = tail.next;
31 }
32 return dummy.next;
33 }
34}Optimal — Single Pass, Wiring Both Links as Each Node Is Created
OptimalBuild the doubly linked structure in one pass instead of two: each new node's .prev is set to whatever the running tail currently is, right at the moment the node is created, and the tail's own .next is pointed forward at that new node in the same step. No second pass is needed because every link a node will ever need is already known the instant it's created.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 static class DNode {
9 int val;
10 DNode next;
11 DNode prev;
12 DNode(int val) { this.val = val; }
13 }
14
15 public Node buildDLL(int[] values) {
16 int n = values.length;
17 if (n == 0) return null;
18 DNode head = new DNode(values[0]);
19 DNode tail = head;
20 for (int i = 1; i < n; i++) {
21 DNode node = new DNode(values[i]);
22 node.prev = tail;
23 tail.next = node;
24 tail = node;
25 }
26 Node dummy = new Node(0);
27 Node outTail = dummy;
28 DNode curr = head;
29 while (curr != null) {
30 outTail.next = new Node(curr.val);
31 outTail = outTail.next;
32 curr = curr.next;
33 }
34 return dummy.next;
35 }
36}