5 Best Ways to Check Whether the Length of a Given Linked List is Even or Odd in Python

Rate this post

πŸ’‘ Problem Formulation: Determining the parity of a linked list length involves checking whether the number of elements it contains is divisible by two (even) or not (odd). Given a linked list, for example, 5 -> 1 -> 7 -> 9, we seek to find out if its length (in this case, 4) is even or odd, returning a simple boolean result.

Method 1: Iterative Counting

This method iteratively traverses through the entire linked list, counting each node until the end is reached. Once traversal is complete, the count is checked to determine if it’s even or odd. The function specification for this method would be is_length_even(head), where head is a reference to the first node of the linked list.

Here’s an example:

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

def is_length_even(head):
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    return count % 2 == 0

# Creating a linked list 5 -> 1 -> 7 -> 9 and checking its length
head = Node(5)
head.next = Node(1)
head.next.next = Node(7)
head.next.next.next = Node(9)
print(is_length_even(head))

Output:

True

This code snippet defines a linked list with a simple Node class and a function is_length_even that returns True if the length is even, False otherwise. It successfully determines the parity by counting each node until the end of the list.

Method 2: Two-Pointer Technique

This technique uses two pointers, fast and slow, where the fast pointer moves two steps at a time and the slow pointer moves one step at a time. If the fast pointer reaches the end of the list or None, the list is of even length; otherwise, it’s odd. The function specification is is_length_even_fast_slow(head).

Here’s an example:

def is_length_even_fast_slow(head):
    fast = head
    while fast and fast.next:
        fast = fast.next.next
    return fast is None

print(is_length_even_fast_slow(head))

Output:

True

This code uses the two-pointer technique, which is generally more efficient as it may only traverse half of the list. The presence of a None at the position of the fast pointer indicates an even length, which efficiently determines the list’s parity.

Method 3: Recursive Approach

By using recursion, one can replace the iteration with a function that calls itself, flipping a boolean value at each call. When the traversal reaches the end, the boolean value indicates the parity of the list. The function signature is is_length_even_recursive(head).

Here’s an example:

def is_length_even_recursive(node, is_even=True):
    if not node:
        return is_even
    return is_length_even_recursive(node.next, not is_even)

print(is_length_even_recursive(head))

Output:

True

The code defines a recursive function that negates a boolean flag with each call. The end of the recursion indicates the list’s length, and the final flag value tells us if the list is even or odd in length. This method is elegant but can hit recursion depth limits for very long lists.

Method 4: Using a Counter Object

Another approach is to encapsulate the count in an object, which can hold state across recursive calls without flipping a boolean. The function signature would be is_length_even_obj(head).

Here’s an example:

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

def is_length_even_obj(node, counter):
    if not node:
        return counter.count % 2 == 0
    counter.count += 1
    return is_length_even_obj(node.next, counter)

counter = Counter()
print(is_length_even_obj(head, counter))

Output:

True

This snippet uses a Counter class to keep track of the length across recursive calls. This method avoids the potential stack overflow issue of deep recursive calls since no call stack is used to keep track of the state.

Bonus One-Liner Method 5: Using List Comprehension

A one-liner using list comprehension involves converting the linked list into a list of nodes and checking the length of that list. While compact, this method bears the cost of additional space complexity. The function signature is is_length_even_list(head).

Here’s an example:

is_length_even_list = lambda head: len([node for node in iter(lambda: head if not (head := head.next) else head, None)]) % 2 == 0

print(is_length_even_list(head))

Output:

True

This one-liner uses a generator expression to iterate through the nodes and creates a list to perform the length check. It’s a compact method but not memory-efficient for large lists, as it constructs an intermediate list corresponding to the linked list.

Summary/Discussion

  • Method 1: Iterative Counting. Simple to understand and implement. However, it has to traverse the entire list, causing O(n) time complexity.
  • Method 2: Two-Pointer Technique. More efficient for larger lists since it potentially traverses only half of the list. However, the method’s concept might be more challenging to grasp for beginners.
  • Method 3: Recursive Approach. Elegant and concise, avoiding iteration. However, it may cause maximum recursion depth exceeded errors for very long lists.
  • Method 4: Using a Counter Object. Stateful and avoids the recursion depth issue. It’s slightly more complex due to the auxiliary class and still requires traversing the entire list.
  • Method 5: Using List Comprehension. A one-liner that is compact and clever, but can be space-intensive for large linked lists due to additional list creation.