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

count = 0
while current:
count += 1
current = current.next
return count % 2 == 0

# Creating a linked list 5 -> 1 -> 7 -> 9 and checking its length

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):
while fast and fast.next:
fast = fast.next.next
return fast is None

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)

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()

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

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.