Search⌘ K
Home
Courses
Recursion for Coding Interviews in Python

Solution Review: Length of a Linked List

Explore how to use recursion to determine the length of a linked list by understanding the base case of an empty list and the recursive case of moving the head pointer forward. Learn to break down the problem into smaller parts and combine results to solve this common data structure challenge effectively.

We'll cover the following...

Solution: Using Recursion

Python 3.5
 import linkedList as l
def length(testVariable, head) :
	# Base case
	if (not head) :
		return 0
		
	# Recursive case
	else :
		return 1 + length(testVariable, head.next) 
# Driver Code
myLinkedList = l.LinkedList() 
myLinkedList.append(3) 
myLinkedList.append(4) 
myLinkedList.append(7) 
myLinkedList.append(11) 
print(length(myLinkedList, myLinkedList.head))

Explanation

The base case for this problem is when a linked list contains no nodes. In this case, we return 00 as the length of that linked list.

For the recursive case, we move the head pointer to its next node, head.next, and call another instance of the same function recursively. When this child function returns, we add 11 to the result.

Our solution is based on the following premise: len ...