Sort a Linked List Using Merge Sort

Introduction Sorting a linked list efficiently is an important problem in data structures. Merge Sort is the best choice for linked lists because it does not require random access like arrays. Problem Statement Given the head of a linked list, sort the list in ascending order using Merge Sort. Why Merge Sort for Linked List? Works efficiently on linked lists Time Complexity: O(n log n) Does not require extra space for shifting elements Approach We use Divide and Conquer: Find the middle of the linked list Divide the list into two halves Recursively sort both halves Merge the sorted halves Python Code python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next # Function to find middle of linked list def get_middle(head): slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next return slow # Function to merge two sorted lists def merge(l1, l2): dummy = ListNode() tail = dummy while l1 and l2: if l1.val < l2.val: ta