Problem

Given a linked list, return the length or size of the linked list.

Examples

1
2
3

Input: head=[1, 2, 8, 3, 7, 0, 4]
Output : 7
Explanation: Given linkedlist has 7 nodes

Solution

Method 1 - Recursive

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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) where n is the length of linked list
  • 🧺 Space complexity: O(n) assuming recursion stack.

Method 2 - Iterative

Code

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

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) where n is the length of linked list
  • 🧺 Space complexity: O(1)