Lecture 189:-Check if a Linked List is Sorted

 

To check if a linked list is sorted in ascending order, we need to traverse the list and compare each element with the next one. If all elements are in ascending order, then the linked list is sorted. Here's how you can implement this check in Python:

 

pythonCopy code

class Node:    def __init__(self, data):        self.data = data        self.next = None class LinkedList:    def __init__(self):        self.head = None    def append(self, data):        new_node = Node(data)        if not self.head:            self.head = new_node        else:            current = self.head            while current.next:                current = current.next            current.next = new_node    def is_sorted(self):        if not self.head or not self.head.next:            return True        current = self.head        while current.next:            if current.data > current.next.data:                return False            current = current.next        return True    def display(self):        current = self.head        while current:            print(current.data, end=" -> ")            current = current.next        print("None") # Example usage: if __name__ == "__main__":    linked_list = LinkedList()    # Append elements to create the linked list    linked_list.append(3)    linked_list.append(7)    linked_list.append(1)    linked_list.append(9)    print("Original Linked List:")    linked_list.display()    if linked_list.is_sorted():        print("The linked list is sorted.")    else:        print("The linked list is not sorted.")

In this example, we have implemented the Node and LinkedList classes. The LinkedList class has an is_sorted method that checks whether the linked list is sorted in ascending order.

We then create a linked list object and use the append method to add elements (3, 7, 1, and 9) to create the linked list. We then call the is_sorted method to check if the linked list is sorted.

The output will be:

rustCopy code

Original Linked List: 3 -> 7 -> 1 -> 9 -> None The linked list is not sorted.

The linked list is not sorted in ascending order since the element 1 is not in the correct position.