PPractick

The problem

The music player shows "12 songs in queue". The queue is a singly linked list and doesn't store its size, so the only way to know is to walk it from the head, counting nodes until you reach nullptr. It's the simplest linked-list traversal, and it's also the building block for many problems that first need the length: finding the middle, removing the n-th node from the end, rotating a list, or comparing two lists' lengths to find where they intersect.

Example: 1 -> 2 -> 3 -> 4 -> 5 → 5.

Function signature

int length(Node* head);            // iterative
int lengthRecursive(Node* head);   // recursive

Test cases

Input list	Output	Explanation
1 -> 2 -> 3 -> 4 -> 5	5
(empty)	0	head is nullptr
9	1
4 -> 4	2	Values don't matter, only nodes

(Confirm: the list is acyclic; an empty list has length 0.)

How interviewers phrase it

• "Count the nodes of a linked list" (GeeksforGeeks).
• "Write it iteratively and recursively."
• As a step inside bigger problems: middle node, n-th from the end, intersection of two lists.

Clarifying questions to ask

1. Could the list have a cycle? (Then a naive count never ends; detect the cycle first.)
2. Is the list very long? (The recursive version uses O(n) stack.)

Follow-ups to expect

1. "Iterative or recursive?"
2. "What if the list has a cycle?"
3. "Can you get the length in O(1)?"
4. "Complexity?"

Related questions

• Introduction to Singly LinkedList Easy
• Insertion at the head of Linked List Easy
• Deletion of the head of LL Easy
• Introduction to Doubly LL Easy
• Insert node before head in Doubly Linked List Easy
• Delete head of Doubly Linked List Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in