Count the nodes of a linked list by walking along it.
What to build
A function length(head) that follows the links.
Requirements
- Complete
length(head)so that it returns the number of nodes. - Do not change the code that builds the list.
Input
The first line has n. The second line has n whole numbers, and it is empty when n is 0.
Output
One number.
Constraints
n is from 0 to 1000.
Example
Input:
3
4 5 6
Output:
3
Why it works
With no index available, the only way to know how long the chain is, is to walk along it to the end.
Examples
Example 1 · Input
3 4 5 6
Expected output
3
Example 2 · Input
1 9
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Start at head and follow next until you reach None.
Hint 2
Add 1 for each node.
Solution
Show one correct solution (try it yourself first)
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def length(head):
count = 0
node = head
while node:
count += 1
node = node.next
return count
n = int(input())
head = None
for value in reversed(input().split()):
head = Node(int(value), head)
print(length(head))