**π‘ Problem Formulation:** You need to determine whether a given linked list is sorted in ascending order. This entails traversing the list and checking if each node’s value is less than or equal to the succeeding node’s value. For instance, given the input `1 -> 2 -> 3 -> 4`

, your function should return `True`

, whereas `1 -> 3 -> 2 -> 4`

should return `False`

.

## Method 1: Iterative Approach

This method involves iteratively traversing the linked list, comparing each node’s value to its successor’s. If we find a node greater than the following node, we immediately return `False`

; if we successfully reach the end, we return `True`

. This check is straightforward, boasting O(n) time complexity and O(1) space complexity because it doesn’t consume extra space for recursive calls.

Here’s an example:

class Node: def __init__(self, value): self.value = value self.next = None def is_sorted_iterative(head): current = head while current and current.next: if current.value > current.next.value: return False current = current.next return True # Creating a sorted linked list head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) print(is_sorted_iterative(head))

Output: `True`

This code snippet creates a simple linked list and then checks if it is sorted using the iterative approach. It returns `True`

if all nodes are in ascending order, which is confirmed by comparing each node to the next one.

## Method 2: Recursive Approach

In this recursive method, we check if the list is sorted by advancing through the list using recursive calls. The base case occurs when the list is empty or contains a single node. We recursively call the function with the next node if the current node satisfies the sorted condition, thus using the call stack as our “iteration.”

Here’s an example:

def is_sorted_recursive(node): if not node or not node.next: return True return node.value <= node.next.value and is_sorted_recursive(node.next) print(is_sorted_recursive(head))

Output: `True`

This code snippet leverages recursion to check if the linked list is sorted. The function checks the current node against its successor and, if ordered correctly, proceeds to check the rest of the list recursively.

## Method 3: Recursive Approach with Helper Function

This method uses a helper function to handle the recursion logic. The main function acts as an initializer, setting up the correct parameters for the recursive helper. This approach promotes better separation of concerns and enhanced readability.

Here’s an example:

def is_sorted_recursive_helper(current, next): if not next: return True return current.value <= next.value and is_sorted_recursive_helper(next, next.next) def is_sorted(head): if not head: return True return is_sorted_recursive_helper(head, head.next) print(is_sorted(head))

Output: `True`

This code utilizes a helper function to recursively determine if the list is sorted, thus simplifying the recursive logic from the main function.

## Bonus One-Liner Method 4: Using Generators

A more Pythonic approach can be achieved using generator expressions. We can create a one-liner that checks adjacent pairs using `zip`

. This method provides code brevity and readability, while still efficiently traversing the linked list.

Here’s an example:

def is_sorted_generator(head): return all(x.value <= y.value for x, y in zip(node_iter(head), node_iter(head.next))) def node_iter(node): while node: yield node node = node.next print(is_sorted_generator(head))

Output: `True`

This code defines a generator function to create an iterator over the nodes in the linked list and then leverages a generator expression alongside `zip`

to check the ordering of each pair of adjacent nodes.

## Summary/Discussion

**Method 1: Iterative Approach.**Strengths: Simplicity, no additional space used. Weaknesses: May require many iterations for long lists.**Method 2: Recursive Approach.**Strengths: Elegant and concise. Weaknesses: Can lead to a stack overflow for very long lists.**Method 3: Recursive Helper Function.**Strengths: Enhanced code readability and modularity. Weaknesses: Similar to the standard recursive approach, it risks stack overflow.**Method 4: Generator Expression.**Strengths: Pythonic, readable, and succinct. Weaknesses: Requires an understanding of advanced Python features like generators.

Emily Rosemary Collins is a tech enthusiast with a strong background in computer science, always staying up-to-date with the latest trends and innovations. Apart from her love for technology, Emily enjoys exploring the great outdoors, participating in local community events, and dedicating her free time to painting and photography. Her interests and passion for personal growth make her an engaging conversationalist and a reliable source of knowledge in the ever-evolving world of technology.