Traverse a Linked List and Collect Its Values
Solve this Problem
Given the
head of a singly linked list, visit every node in order and return an array of its values, head to tail.
Traversal is the operation nearly every other linked list algorithm is built on — search, length, printing, and copying all boil down to "visit each node once." Both the iterativeIterativeSolved with an explicit loop, keeping state (like a curr pointer) in local variables instead of the call stack. and recursiveRecursiveSolved by having the function call itself on a smaller version of the same problem — here, "collect the rest of the list" is the same problem as the original, just one node shorter. versions visit every node exactly once; the recursive version just spends extra call-stack space doing it.
Test Case 1:
Input:head = [10, 20, 30, 40]
Output:[10, 20, 30, 40]
Explanation:Every node's value, collected in list order.
Test Case 2:
Input:head = [5]
Output:[5]
Explanation:A single-node list collects into a single-element array.
Test Case 3:
Input:head = []
Output:[]
Explanation:Nothing to visit — the result is empty.
Constraints
- ◆
0 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
Traversing an empty list must return an empty array
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public List<Integer> traverseLinkedList(Node head) { |
| 3 | List<Integer> result = new ArrayList<>(); |
| 4 | Node curr = head; |
| 5 | while (curr != null) { |
| 6 | result.add(curr.val); |
| 7 | curr = curr.next; |
| 8 | } |
| 9 | return result; |
| 10 | } |
| 11 | } |
| 12 |
Linked Listnull
10
curr
20
30
40
Array
Variables
result
[]INITIALIZE
curr starts at head, and result starts as an empty collector.
Step 1 / 10
Approach & Solutions
Recursive — Accumulate on the Way Down
GoodA shared result collector is passed into every recursive call. Each call checks whether node is null (nothing left to visit); if not, it appends node.val and recurses on node.next. Every node is still visited exactly once, but each call adds a stack frame, so this uses O(n) call-stack space on top of the output itself.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public List<Integer> traverseLinkedList(Node head) {
9 List<Integer> result = new ArrayList<>();
10 collect(head, result);
11 return result;
12 }
13
14 private void collect(Node node, List<Integer> result) {
15 if (node == null) {
16 return;
17 }
18 result.add(node.val);
19 collect(node.next, result);
20 }
21}Iterative — Single Pass
OptimalWalk curr from head, appending each node's val onto result and advancing. Same total work as the recursive version — every node still gets collected — but with no call-stack overhead beyond the output array itself.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public List<Integer> traverseLinkedList(Node head) {
9 List<Integer> result = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 result.add(curr.val);
13 curr = curr.next;
14 }
15 return result;
16 }
17}