# Solution For Sort List

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

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

right = sortList(nextMiddle)

return merge(left, right)
``````

``````slow = head

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.

## Step by Step Implementation For Sort List

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// check for empty or single element list
}

// find the middle of the list
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// split the list into two halves
slow.next = null;

// sort each half recursively

// merge the two sorted halves
}

// create a dummy node to store the merged list
ListNode dummy = new ListNode();
ListNode tail = dummy;

// loop through both lists and add the smaller element to the merged list
} else {
}
tail = tail.next;
}

// add the remaining elements to the merged list
}
}

return dummy.next;
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
# check for empty list

# split the list in two halves
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None

# sort each half recursively
l2 = self.sortList(second)

# merge the two sorted halves
return self.merge(l1, l2)

def merge(self, l1, l2):
# create a new node to head the merged list
dummy = curr = ListNode()
# compare nodes of l1 and l2 and append the smaller node to the merged list
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# append the remaining nodes of l1 or l2 to the merged list
curr.next = l1 or l2
return dummy.next```
```/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/

while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}

const mid = slow.next;
slow.next = null;

};

function merge(l1, l2) {
let dummy = new ListNode();
let curr = dummy;

while (l1 && l2) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}

curr.next = l1 || l2;

return dummy.next;
}```
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
ListNode *l2 = sortList(slow);
return merge(l1, l2);
}

ListNode* merge(ListNode *l1, ListNode *l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = merge(l1->next, l2);
return l1;
}
l2->next = merge(l1, l2->next);
return l2;
}
};```
```/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
// check for empty or single element list
{
}

// find the middle of the list

// split the list into two halves
ListNode right = middle.next;
middle.next = null;

// sort each half
left = SortList(left);
right = SortList(right);

// merge the sorted halves
return MergeLists(left, right);
}

{
// slow and fast pointers to find the middle of the list

// move fast pointer by two nodes and slow pointer by one node
// at the end of the loop, slow pointer will point to the middle of the list
while (fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}

return slow;
}

private ListNode MergeLists(ListNode left, ListNode right)
{
// create a new dummy node to store the merged list
ListNode dummy = new ListNode();

// create a pointer to traverse the dummy node
ListNode current = dummy;

// while there are still nodes in the left and right lists
while (left != null && right != null)
{
// if the value in the left list is less than the value in the right list
if (left.val <= right.val)
{
// add the node from the left list to the merged list
current.next = left;

// move the left pointer to the next node in the left list
left = left.next;
}
else
{
// add the node from the right list to the merged list
current.next = right;

// move the right pointer to the next node in the right list
right = right.next;
}

// move the pointer to the next node in the merged list
current = current.next;
}

// if there are still nodes in the left list
if (left != null)
{
// add the remaining nodes from the left list to the merged list
current.next = left;
}

// if there are still nodes in the right list
if (right != null)
{
// add the remaining nodes from the right list to the merged list
current.next = right;
}

// return the merged list
return dummy.next;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]