π‘ 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.