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):
        self.data = data
        self.next = 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
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def merge_sort(self, head):
        if head is None or head.next is None:
            return head
        middle = self.get_middle(head)
        next_to_middle = middle.next
        middle.next = 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 fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow

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

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

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

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(4)
linked_list.append(2)
linked_list.append(1)
linked_list.append(3)
print("Linked list before sorting:")
linked_list.traverse()  # Output: 4 -> 2 -> 1 -> 3 -> None
linked_list.sort()
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.