Efficient Approaches to Print Alternate Nodes in a Linked List Recursively

by

💡 Problem Formulation: The challenge is to create a Python program that traverses a singly linked list and prints out alternate nodes using recursion. For instance, given a linked list with nodes containing the values 1, 2, 3, 4, 5, the expected output should display the values 1, 3, 5, which represent every other node starting from the head.

Method 1: Use Recursion with a Counter

This method involves using a helper function that accepts the current node and a counter as parameters. The counter is used to determine whether a node is at an even or odd index. If the counter is odd, the node’s data is printed. After printing a node’s data, the method is recursively called on the next node with the counter incremented.

Here’s an example:

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

def print_alternate(node, counter=1):
    if node is None:
        return
    if counter % 2 == 1:
        print(node.data)
    print_alternate(node.next, counter + 1)

# Create a simple linked list 1->2->3->4->5 and test the function
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

print_alternate(head)

Output:

1
3
5

The provided snippet defines a Node class and a print_alternate function that uses recursion to print the data of every other node, starting from an arbitrary head of a linked list. The counter is incremented with each recursive call and is used to check the position of the node. The position alternates, hence printing every alternate node.

Method 2: Use Recursion with Skip Logic

In this approach, we avoid using an explicit counter variable. Instead, we leverage the call stack inherent in recursion to skip every other node. This is done by adding an extra recursive call that effectively moves two nodes forward on each step instead of one, hence printing alternate nodes.

Here’s an example:

def print_alternate(node):
    if node is None:
        return
    print(node.data)
    if node.next is not None:
        print_alternate(node.next.next)

# Assuming the same linked list and Node class as above
print_alternate(head)

Output:

1
3
5

This method revolves around calling the print_alternate function recursively but with the next node’s next pointer, i.e., one additional step forward, which skips printing every second node and hence achieves the goal of printing alternate nodes.

Method 3: Toggle a Boolean Flag

Another solution is to use a boolean flag that toggles with every recursive call. When the flag is true, print the node’s data; otherwise, skip the node. On each recursive call, the flag is negated, ensuring that alternate nodes are printed.

Here’s an example:

def print_alternate(node, should_print=True):
    if node is None:
        return
    if should_print:
        print(node.data)
    print_alternate(node.next, not should_print)
    
# Assuming the same linked list and Node class as above
print_alternate(head)

Output:

1
3
5

In this snippet, a boolean flag gets toggled on each recursion call. The flag determines whether to print the current node. By alternating the flag’s value between true and false with each recursive step, we ensure alternate nodes get printed.

Method 4: Recurse with Odd Index Removal

This technique involves modifying the linked list as it is traversed. Every recursive call removes the next node (if exists) before proceeding, effectively transforming the list into one containing only alternate nodes. After the list is modified, the remaining nodes are printed.

Here’s an example:

def print_alternate(node):
    if node is None:
        return
    print(node.data)
    if node.next is not None:
        node.next = node.next.next
        print_alternate(node.next)
        
# Assuming the same linked list and Node class as above
print_alternate(head)

Output:

1
3
5

This approach mutates the original list by severing the next pointer of every node encountered, thus removing every other node from the list recursively. After applying this operation, the function then prints each node from the mutated list, resulting in alternate nodes being printed from the original list.

Bonus One-Liner Method 5: Using a Python Generator

While not purely recursive, this method employs a generator to yield alternate nodes in a single line of Python. It’s an elegant solution for users familiar with Python’s advanced features.

Here’s an example:

def print_alternate(node):
    print(*(node.data for index, node in enumerate(iter(lambda: node if not node or (node:=node.next) and node.next and not (node:=node.next) else None, None)) if index % 2 == 0))
    
# Assuming the same linked list and Node class as above
print_alternate(head)

Output:

1 3 5

This one-liner compacts the logic of printing alternate nodes into a single generator expression, coupled with a lambda function that advances two steps through the list on each invocation. It’s a clever trick but sacrifices readability for brevity.

Summary/Discussion

  • Method 1: Counter-Based Recursion. Strengths: Intuitive and straightforward. Weaknesses: Requires additional parameter for counting.
  • Method 2: Skip Logic Recursion. Strengths: Reduces parameter burden by using recursion creatively. Weaknesses: May not be immediately clear to beginners.
  • Method 3: Boolean Flag Toggle. Strengths: Simple and does not alter list structure. Weaknesses: Toggle logic can be confusing to some.
  • Method 4: Odd Index Removal. Strengths: Operates in-place without additional parameters. Weaknesses: Mutates the original list, which can be undesirable.
  • One-Liner Method 5: Python Generator Expression. Strengths: Elegant and concise. Weaknesses: Poor readability and more challenging to understand.