Find the Length of a Linked List
Solve this Problem
Given the
head of a singly linked list, return the number of nodes it contains.
A linked list has no length field of its own — the only way to know how many nodes it has is to visit them. Both solutions do exactly that: the iterativeIterativeSolved with an explicit loop, keeping a running count in a local variable instead of the call stack. version keeps a running count in a local variable, while the recursiveRecursiveSolved by having the function call itself on a smaller version of the same problem — "the length of the rest of the list" is the same problem, just one node shorter — with each call contributing 1 for its own node. version builds the count as 1 + (length of everything after this node), accumulating the total as each call returns.
Test Case 1:
Input:head = [3, 6, 9, 2, 5]
Output:5
Explanation:Five nodes, so the length is 5.
Test Case 2:
Input:head = [7]
Output:1
Explanation:A single node has length 1.
Test Case 3:
Input:head = []
Output:0
Explanation:An empty list has length 0.
Constraints
- ◆
0 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
An empty list has length 0
🚀
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 int lengthOfLinkedList(Node head) { |
| 3 | int count = 0; |
| 4 | Node curr = head; |
| 5 | while (curr != null) { |
| 6 | count++; |
| 7 | curr = curr.next; |
| 8 | } |
| 9 | return count; |
| 10 | } |
| 11 | } |
| 12 |
3
curr
6
9
2
5
Variables
count
0curr
3INITIALIZE
count starts at 0, and curr starts at head.
Step 1 / 12
Approach & Solutions
Recursive — 1 + Length of the Rest
GoodAn empty list (head is null) has length 0. Otherwise, the length is 1 (for the current node) plus the length of everything after it — head.next. Each call is only responsible for counting its own node and trusting the recursive call to correctly count the rest. Elegant, but each call adds a stack frame, so this costs O(n) call-stack space.
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 int lengthOfLinkedList(Node head) {
9 if (head == null) {
10 return 0;
11 }
12 return 1 + lengthOfLinkedList(head.next);
13 }
14}Iterative — Count While Traversing
OptimalWalk curr from head, incrementing count once per node. Same total work as the recursive version, but with no call-stack overhead — the running count lives in a single local variable.
Time
O(n)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public int lengthOfLinkedList(Node head) {
9 int count = 0;
10 Node curr = head;
11 while (curr != null) {
12 count++;
13 curr = curr.next;
14 }
15 return count;
16 }
17}