Algorithm to check if a linked list is sorted

A linked list is a linear data structure in which the elements are not stored at contiguous memory locations like arrays but they are stored in random locations in heap memory because the memory for each node of the linked list has to be dynamically allocated and these nodes are connected to each other by links or reference.

In this article, we have explored an algorithm to check if a given Linked List is sorted or not in linear time O(N). It takes constant space O(1).

Structure of a node of our Linked List

Each node consists of a integer type data and a self-referential structure.

/* Linked list node */
struct Node 
{ 
    // integer data
    int data;
    // self-referential structure to link multiple nodes
    struct Node* next; 
}; 

Question: Given a Linked List, check whether the Linked List is sorted or not?

Sample Testcase:

Input  : 1 -> 3 -> 4 -> 7 -> 8
Output : Yes
Explanation :
In given linked list, starting from head,
1 < 3 < 4 < 7 < 8 . So, it is sorted.

Input  : 24 -> 12 -> 9 -> 1 -> 8 -> 2
Output : No

Approach to solve:

We have to check if the elements in the linked list are in sorted order. So, we'll traverse the linked list and check whether the next element is greater than the previous element, if this condition holds true for the entire linked list, it's sorted otherwise the list isn't sorted.

Iterative Approach :

bool isSorted(struct Node *head) 
{  
    if (head == NULL) 
        return true; 
    
    for (Node *t=head; t->next != NULL; t=t->next) 
       if (t->data > t->next->data) 
            return false; 
            
    return true; 
} 

Explanation

    if (head == NULL)
        return true;

If the head points to NULL which means that the linked list is empty, then we return true meaning that the linked list is sorted.

    for (Node *t=head; t->next != NULL; t=t->next) 
       if (t->data > t->next->data) 
            return false;       
    return true; 

We loop through the entire linked list and for each node we check if the value in current node is greater than the value in next node. If this is true, then the linked list is not sorted and we return false. If the condition never became true throughout the entire linked list, then we return true which means that the linked list is sorted.

Complexity Analysis -

The asymptotic complexity is what we'll be analyzing, that is, how the complexity of our code grows with the size of our input. Let's consider the total nodes in our linked list is n.
Time Complexity comes out to be O(n) and Space Complexity is O(1) because we are traversing the linked list once and checking the condition if the linked list is sorted and so, the code will learn in linear time and takes constant time as we're not using any extra space during the traversal of list.

Recursive Approach :

bool isSorted(struct Node *head) 
{  
    // Base case 
    if (head == NULL || head->next == NULL) 
        return true; 
      
    // Check first two nodes and recursively call for next node.
    return ((head->data > head->next->data) && isSorted(head->next)); 
}

Explanation

    if (head == NULL || head->next == NULL) 
        return true; 

This is the base condition of the recursive code. If the head becomes NULL or the next element to the head points to NULL, we return true which means the linked list is sorted and the condition to check for sorted element has not returned false yet.

    return ((head->data < head->next->data) && 
             isSorted(head->next));

we check if the data of current element is less than the data of next node, if it's true then next condition will execute and we'll call the function for the next node. If the condition is false, the function will return false because the condition of being sorted is false.

Complexity Analysis

The asymptotic complexity is what we'll be analyzing, that is, how the complexity of our code grows with the size of our input. Let's consider the total nodes in our linked list is n.

Time Complexity comes out to be O(n) and Space Complexity is O(n) as well because we are traversing the linked list once but we're doing it recursively and as we know recursion internally uses pile of stack data structures to keep track of the state of each function call. As the recursion starts running, stack gets created per function call and keeps on increasing until we hit the base condition or return any value and after that stack unwinding takes place and after each call, one stack gets popped.