Find the Length of a Linked List

Given the head of a singly linked list, return the number of nodes in it.

Example 1

Text

Input:  4 -> 10 -> 40 -> 5
Output: 4

Example 2

Text

Input:  empty list
Output: 0

A linked list made of bare nodes doesn't store its length (unlike ArrayList, where size() is O(1)), so we have to walk it and count. The nodes here use null for "no next node" and have mutable fields, so no wrapper types are needed.

Brute force: recursion

An empty list has length 0. Any other list has length 1 + length(rest).

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static int length(ListNode head) {
        if (head == null) return 0;
        return 1 + length(head.next);
    }

    public static void main(String[] args) {
        System.out.println(length(fromArray(4, 10, 40, 5)) + " " + length(null));
    }
}

Output

4 0

Time: O(n). Space: O(n): the + 1 happens after the recursive call returns, so every frame stays on the stack until the end of the list is reached. A list long enough to exhaust the thread stack makes this version throw StackOverflowError.

Optimal: iterate and count

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static int length(ListNode head) {
        int count = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(length(fromArray(4, 10, 40, 5)) + " " + length(null));
        int[] values = new int[200_000];
        for (int i = 0; i < values.length; i++) values[i] = i;
        System.out.println(length(fromArray(values)));
    }
}

Output

4 0
200000

Time: O(n). Space: O(1). The iterative version handles a 200,000-node list without recursion.

The 200,000-node list is counted without recursion, so the stack does not grow with the list length. The garbage collector reclaims the nodes once nothing references them.

Why counting matters: the two-pass technique

Knowing the length turns a position counted from the end into a position counted from the start: the node that is n from the end is at index length - n. A first pass counts, and a second pass walks to that index. Two O(n) passes are still O(n). The Middle of the Linked List and Nth Node From the End lessons work with such positions.