💡 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.