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

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.