Problem
Given a linked list, return the length or size of the linked list.
Examples
Input: head=[1, 2, 8, 3, 7, 0, 4]
Output : 7
Explanation: Given linkedlist has 7 nodes
Solution
Method 1 - Recursive
Code
Java
class Solution {
public int size(ListNode head) {
// Base case: if the head is null, return 0
if (head == null) {
return 0;
}
// Recursive case: 1 + length of the rest of the list
return 1 + size(head.next);
}
}
Complexity
- ⏰ Time complexity:
O(n)
wheren
is the length of linked list - 🧺 Space complexity:
O(n)
assuming recursion stack.
Method 2 - Iterative
Code
Java
class Solution {
public int size(ListNode head) {
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
}
Complexity
- ⏰ Time complexity:
O(n)
wheren
is the length of linked list - 🧺 Space complexity:
O(1)