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:
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
SOCIAL SHARE CARD GENERATOR