Algorithms to Compute the Length of a Linked List

Given a singly linked list node, return its length. The linked list has fields next and val.

Constraints
n ≤ 100,000 where n is the number of nodes in node

Example 1
Input
node =
5 – 4 – 3
Output
3
Explanation
This linked list has 3 nodes.

Example 2
Input
node =
1 – 2
Output
2
Explanation
This linked list has 2 nodes.

Recursive Algorithm to Follow and Count the Nodes in a Linked List

We can use the two-liner recursion to follow and count the nodes in the linked list. Please note that most compilers will optimise this Tail Recursion into iterative calls.

C++ Recursion to count the nodes in a Linked List.

1
2
3
4
5
6
7
8
9
10
11

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int countNodes(LLNode* node) {
    if (!node) return 0;
    return 1 + countNodes(node->next);
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int countNodes(LLNode* node) {
    if (!node) return 0;
    return 1 + countNodes(node->next);
}

And you can do this in one-liner recursion in Python:

1
2
3
4
5
6
7

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def countNodes(self, node):
        return 1 + self.countNodes(node.next) if node is not None else 0

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def countNodes(self, node):
        return 1 + self.countNodes(node.next) if node is not None else 0

Iterative Algorithm to Count the Nodes in a Linked List

While you can perfectly do this in iteration, just following the node and count them until we reach the end/tail.

C++ implementation of iterative algorithm to count the nodes in Linked List.

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

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int countNodes(LLNode* node) {
    int r = 0;
    while (node) {
        r ++;
        node = node->next;
    }
    return r;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
int countNodes(LLNode* node) {
    int r = 0;
    while (node) {
        r ++;
        node = node->next;
    }
    return r;
}

Python solution to count the linked list nodes in iterative manner:

1
2
3
4
5
6
7
8
9
10
11

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def countNodes(self, node):
        ans = 0
        while node:
            ans += 1
            node = node.next
        return ans

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def countNodes(self, node):
        ans = 0
        while node:
            ans += 1
            node = node.next
        return ans

All implementations are O(N) time and O(1) space – assuming the Recursion will be tail-optimised.

Length of a Linked List Algorithm

• Algorithms to Compute the Length of a Linked List
• Teaching Kids Programming – Compute the Kth Last Node of a Linked List (and Length of a Linked List)
• Teaching Kisd Programming – Finding the Length of a Linked List (Recursion and Iterative Algorithm)

–EOF (The Ultimate Computing & Technology Blog)