Sort List - Leetcode Solution

Problem Statement: Given the head of a linked list, return the list after sorting it in ascending order.

Example 1: Input: head = [4,2,1,3] Output: [1,2,3,4]

Example 2: Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]

Approach: We can use merge sort algorithm for sorting linked lists. Merge sort is an efficient and general-purpose algorithm that works well for linked lists.

Merge sort algorithm involves the following steps:

1. Divide the list into two equal halves.
2. Recursively sort the two halves.
3. Merge the sorted halves.

We will achieve this using two functions:

1. The function "sortList" will be the driver function that will call the "mergeSort" function recursively.
2. The function "mergeSort" will divide the linked list into two halves, sort them recursively, and then merge the two sorted halves.

Here is the detailed solution in Python that implements the above approach:

class ListNode: def init(self, val=0, next=None): self.val = val self.next = next

def sortList(head: ListNode) -> ListNode: if head is None or head.next is None: return head

middle = findMiddle(head)
nextMiddle = middle.next
middle.next = None

left = sortList(head)
right = sortList(nextMiddle)

return merge(left, right)

def findMiddle(head): if head is None: return head

slow = head
fast = head.next

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

return slow

def merge(left, right): if left is None: return right if right is None: return left

if left.val < right.val:
    left.next = merge(left.next, right)
    return left
else:
    right.next = merge(left, right.next)
    return right

The "findMiddle" function finds the middle node of the linked list and returns it. The "merge" function merges two sorted linked lists and returns the merged list. The "sortList" function recursively sorts the linked list by calling the "mergeSort" function and returns the sorted list.

The overall time complexity of this algorithm is O(n log n), where n is the length of the linked list, as this is the time complexity of merge sort. The space complexity of this algorithm is O(log n) due to the recursive stack calls.

1