## Similar Problems

Similar Problems not available

# Sort List - Leetcode Solution

## Companies:

LeetCode: Sort List Leetcode Solution

Difficulty: Medium

Topics: linked-list sorting two-pointers

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:

- Divide the list into two equal halves.
- Recursively sort the two halves.
- Merge the sorted halves.

We will achieve this using two functions:

- The function "sortList" will be the driver function that will call the "mergeSort" function recursively.
- 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.

## Sort List Solution Code

`1`