Sort a Singly Linked List

Sorting a Singly Linked List

Sorting a singly linked list involves arranging the nodes in the list in a specific order, typically in ascending or descending order. This can be achieved using various sorting algorithms adapted for linked lists. Common algorithms for sorting linked lists include merge sort and bubble sort.

Step-by-Step Process for Merge Sort

Merge sort is an efficient, stable, and comparison-based sorting algorithm that works well with linked lists due to its divide-and-conquer approach. The process involves recursively splitting the list into halves, sorting each half, and merging the sorted halves.

  1. Split the List: Use the slow and fast pointer technique to find the middle of the list and split it into two halves.
  2. Sort Each Half: Recursively sort each half of the list.
  3. Merge Sorted Halves: Merge the two sorted halves into a single sorted list.

Consider a singly linked list with the following structure before sorting:

Head -> 4 -> 2 -> 1 -> 3 -> None

After sorting, the list will become:

Head -> 1 -> 2 -> 3 -> 4 -> None

Python Program to Sort a Singly Linked List using Merge Sort

class Node:
    def __init__(self, data): = data = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            current = self.head
                current =
   = new_node

    def merge_sort(self, head):
        if head is None or is None:
            return head
        middle = self.get_middle(head)
        next_to_middle = = None
        left = self.merge_sort(head)
        right = self.merge_sort(next_to_middle)
        sorted_list = self.sorted_merge(left, right)
        return sorted_list

    def get_middle(self, head):
        if head is None:
            return head
        slow = head
        fast = head
        while and
            slow =
            fast =
        return slow

    def sorted_merge(self, a, b):
        result = None
        if a is None:
            return b
        if b is None:
            return a
        if <=
            result = a
   = self.sorted_merge(, b)
            result = b
   = self.sorted_merge(a,
        return result

    def sort(self):
        self.head = self.merge_sort(self.head)

    def traverse(self):
        current = self.head
        while current:
            print(, end=" -> ")
            current =

# Example usage:
linked_list = SinglyLinkedList()
print("Linked list before sorting:")
linked_list.traverse()  # Output: 4 -> 2 -> 1 -> 3 -> None
print("Linked list after sorting:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> None

This Python program defines a singly linked list with methods for appending nodes, sorting the list using merge sort, and traversing the list. The merge_sort method recursively splits the list into halves, sorts each half, and merges the sorted halves to produce a sorted list.