Exploring Recursive Strategies to Find the Length of a Linked List in Python

Rate this post

πŸ’‘ Problem Formulation: In this article, we tackle the challenge of determining the length of a linked list using recursion in Python. Specifically, we aim to write a Python function that, given the head node of a singly linked list, returns the number of nodes it contains. For instance, inputting a linked list with nodes [1, 2, 3, 4] should yield an output of 4, as there are four nodes in the list.

Method 1: Classic Recursive Approach

This classic recursive method involves a function that calls itself with the next node until it reaches the end of the linked list. The function definition is def find_length_recursive(node):, which returns the length of the linked list starting from the given node.

Here’s an example:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_length_recursive(node):
    if not node:
        return 0
    return 1 + find_length_recursive(node.next)

# Example LinkedList: 1->2->3->4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(find_length_recursive(head))

Output:

4

The function find_length_recursive() checks if the current node is None, the base case indicating the end of the list, and returns 0. Otherwise, it returns 1 plus the result of calling itself on the next node, effectively counting each node in the chain.

Method 2: Tail Recursive Approach

Tail recursion optimizes the classic approach by passing the accumulated length along with the next node to avoid adding stack frames. We define a helper function within our main function, def find_length_tail_recursive(node):, to implement this strategy.

Here’s an example:

def find_length_tail_recursive(node):
    def recurse(node, count):
        if not node:
            return count
        return recurse(node.next, count + 1)
    return recurse(node, 0)

# Example LinkedList: 1->2->3->4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(find_length_tail_recursive(head))

Output:

4

The inner function recurse() is defined within find_length_tail_recursive() and adds a parameter count which holds the current length of the list as the recursion unwinds. When the base case is reached, the accumulated count is returned.

Method 3: External Counter Approach

Instead of passing the count within the recursive calls, we can use an external counter that gets updated with each recursion. This method also defines a recursive function: def find_length_external_counter(node, count): which modifies the external counter to compute the length.

Here’s an example:

count = 0

def find_length_external_counter(node):
    global count
    if not node:
        return count
    count += 1
    return find_length_external_counter(node.next)

# Example LinkedList: 1->2->3->4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(find_length_external_counter(head))

Output:

4

The global variable count keeps track of the length of the linked list. With each recursive call of find_length_external_counter(), count is incremented until the end of the list is reached.

Method 4: Class Attribute Approach

Another way to track the length is by using a class attribute to store the count. This approach uses a class with a recursive method, find_length_class_attribute(self, node):, to encapsulate the linked list and its length logic.

Here’s an example:

class LinkedList:
    def __init__(self):
        self.count = 0

    def find_length_class_attribute(self, node):
        if not node:
            return self.count
        self.count += 1
        return self.find_length_class_attribute(node.next)

# Example LinkedList: 1->2->3->4
llist = LinkedList()
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(llist.find_length_class_attribute(head))

Output:

4

The LinkedList class has an attribute count which is updated by the method find_length_class_attribute() as it recursively processes each node. Upon reaching the end of the list, count reflects the total length.

Bonus One-Liner Method 5: Recursive Lambda Function

The quintessence of brevity, this method uses a recursive lambda function to determine the length. The one-liner solution is defined as find_length_lambda = lambda node: 0 if not node else 1 + find_length_lambda(node.next), making it a concise and elegant approach.

Here’s an example:

find_length_lambda = lambda node: 0 if not node else 1 + find_length_lambda(node.next)

# Example LinkedList: 1->2->3->4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(find_length_lambda(head))

Output:

4

The lambda function find_length_lambda operates similarly to the classic recursive method but in a compact form. It uses a ternary conditional operator to return 0 for the base case, or 1 plus the recursive call on the next node otherwise.

Summary/Discussion

  • Method 1: Classic Recursive Approach. Strengths: Simple and clear. Weaknesses: Basic recursion can lead to stack overflow for long lists.
  • Method 2: Tail Recursive Approach. Strengths: Optimized stack usage. Weaknesses: Python does not inherently optimize tail recursion like some other languages.
  • Method 3: External Counter Approach. Strengths: Removes the need for additional parameters. Weaknesses: Relies on global state, which can lead to bugs.
  • Method 4: Class Attribute Approach. Strengths: Encapsulates state within a class. Weaknesses: Requires an additional class structure.
  • Method 5: Recursive Lambda Function. Strengths: Extremely concise. Weaknesses: May be less readable for those unfamiliar with lambda functions or recursion.