Given the head of a Linked List, return the length of the list.
Example:
Explanation: There are 5 nodes in the Linked List.
listLength(ListNode.of([1, 2, 3, 4, 5]))
# 5listLength(ListNode.of([1, 2]))
# 2listLength(ListNode.of([1, 1, 1]))
# 3We can walk along the Linked List and count the number of nodes we've seen so far. We'll return the count at the end.
def listLength(head):
count = 0
node = head
# while the node isn't null
while node:
count = count + 1 # add 1 to count
node = node.next # step to next node
return countTime Complexity O(n). We have to step through every node in the Linked List. If there are n nodes in the Linked List, we have to do n total steps. This means the total number of operations we have to do is O(n).
Space Complexity O(1). Our algorithm uses 2 variables, called count and node. This means we have to store O(2) variables, which is the same as O(1) variables. Remember, O(1) means the memory doesn't depend on the size of the array. As n gets big, the amount of memory grows like the number 1 does - not at all.