Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Length of a linked list

EASYProblemSolveExternal Links

Description

Given the head of a singly linked list, find the length of the linked list.

The length is defined as the total number of nodes present in the list. Each node contains a data value and a pointer to the next node. The last node points to null, marking the end of the list.

Return an integer representing the count of nodes.

Examples

Example 1

Input: head: 1 → 2 → 3 → 4 → 5

Output: 5

Explanation: Starting from the head node with value 1, we traverse through nodes 2, 3, 4, and 5 before reaching null. That gives us a total of 5 nodes in the list.

Example 2

Input: head: 2 → 4 → 6 → 7 → 5 → 1 → 0

Output: 7

Explanation: We visit each node one by one — 2, 4, 6, 7, 5, 1, 0 — counting 7 nodes total before reaching null.

Example 3

Input: head: 10

Output: 1

Explanation: The linked list has a single node with value 10. Its next pointer is null, so the length is 1.

Constraints

  • 1 ≤ number of nodes ≤ 4 × 10^4
  • 1 ≤ node.data ≤ 10^3

Editorial

Brute Force

Intuition

Unlike arrays, linked lists do not store their size anywhere. There is no .length property you can read — the only way to know how many nodes exist is to physically visit each one.

Think of it like counting houses on a street where you can only see one house at a time. You start at the first house, take one step forward to the next house, take another step forward, and keep counting until there are no more houses ahead. The number of steps you took (plus one for the starting house) gives you the total count.

This is the most natural and only approach: start at the head, walk forward node by node, and increment a counter each time you visit a node. When you reach null (meaning there is no next node), you stop and return the counter.

Since every node must be visited exactly once, there is no way to do this faster than O(n) — there is no shortcut that skips nodes. This simple traversal IS the optimal solution.

Step-by-Step Explanation

Let's trace through with head: 1 → 2 → 3 → 4 → 5:

Step 1: Initialize count = 0. Set a pointer curr to the head node (value 1). The pointer is not null, so we enter the loop.

Step 2: Visit node with value 1. Increment count to 1. Move curr to the next node (value 2).

Step 3: Visit node with value 2. Increment count to 2. Move curr to the next node (value 3).

Step 4: Visit node with value 3. Increment count to 3. Move curr to the next node (value 4).

Step 5: Visit node with value 4. Increment count to 4. Move curr to the next node (value 5).

Step 6: Visit node with value 5. Increment count to 5. Move curr to the next node, which is null.

Step 7: curr is null — we've gone past the last node. Exit the loop and return count = 5.

Counting Nodes by Traversing the Linked List — Watch how the curr pointer moves through each node, incrementing the count at every stop, until it reaches null.

Algorithm

  1. Initialize a counter count = 0.
  2. Set a pointer curr to the head of the linked list.
  3. While curr is not null:
    a. Increment count by 1.
    b. Move curr to curr.next.
  4. Return count.

Code

class Solution {
public:
    int getCount(Node* head) {
        int count = 0;
        Node* curr = head;
        
        while (curr != nullptr) {
            count++;
            curr = curr->next;
        }
        
        return count;
    }
};
class Solution:
    def getCount(self, head: Node) -> int:
        count = 0
        curr = head
        
        while curr is not None:
            count += 1
            curr = curr.next
        
        return count
class Solution {
    public int getCount(Node head) {
        int count = 0;
        Node curr = head;
        
        while (curr != null) {
            count++;
            curr = curr.next;
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the entire linked list exactly once, visiting each of the n nodes one time. Each node visit involves a constant-time counter increment and a pointer advance. Therefore, the total work is proportional to the number of nodes: O(n).

This is the best possible time complexity for this problem because we cannot know the count without visiting every node — there is no random access in a linked list.

Space Complexity: O(1)

We use only two variables regardless of the list size: a counter count and a pointer curr. No additional data structures are created, so the space usage is constant.