VOOZH about

URL: https://dev.to/dharani_boominathan_b1e6b/sort-a-linked-list-using-merge-sort-30h0

⇱ Sort a Linked List Using Merge Sort - DEV Community

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:

  1. Find the middle of the linked list
  2. Divide the list into two halves
  3. Recursively sort both halves
  4. 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:
 tail.next = l1
 l1 = l1.next
 else:
 tail.next = l2
 l2 = l2.next
 tail = tail.next

 tail.next = l1 if l1 else l2
 return dummy.next

# Merge Sort function
def merge_sort(head):
 if not head or not head.next:
 return head

 mid = get_middle(head)
 right = mid.next
 mid.next = None

 left = merge_sort(head)
 right = merge_sort(right)

 return merge(left, right)

## Input
 4-> 2-> 1-> 3

## output
 1 -> 2 -> 3 -> 4