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 nodeExample 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)
loading...
Last Post: Teaching Kids Programming - Binary Search Algorithm to Compute the Logarithm Base Two Function
Next Post: Binary Search Algorithm to Find the Fixed Point