# 5 Best Ways to Check If a Linked List Is Sorted in Python

Rate this post

π‘ 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

while current and current.next:
if current.value > current.next.value:
return False
current = current.next
return True

# Creating a sorted linked list

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)

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)

return True

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

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.