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:
- Divide the list into two equal halves.
- Recursively sort the two halves.
- 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.
Step by Step Implementation For Sort List
/**
* Definition for singly-linked 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 {
public ListNode sortList(ListNode head) {
// check for empty or single element list
if (head == null || head.next == null) {
return head;
}
// find the middle of the list
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// split the list into two halves
ListNode head1 = head;
ListNode head2 = slow.next;
slow.next = null;
// sort each half recursively
head1 = sortList(head1);
head2 = sortList(head2);
// merge the two sorted halves
return merge(head1, head2);
}
private ListNode merge(ListNode head1, ListNode head2) {
// 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
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tail.next = head1;
head1 = head1.next;
} else {
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
}
// add the remaining elements to the merged list
if (head1 != null) {
tail.next = head1;
}
if (head2 != null) {
tail.next = head2;
}
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
if not head or not head.next:
return head
# split the list in two halves
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
# sort each half recursively
l1 = self.sortList(head)
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/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function(head) {
if (!head || !head.next) return head;
let slow = head, fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
const mid = slow.next;
slow.next = null;
return merge(sortList(head), sortList(mid));
};
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;
}/**
* Definition for singly-linked list.
* 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:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head, *prev = NULL;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
ListNode *l1 = sortList(head);
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;
}
};/**
* Definition for singly-linked list.
* 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 {
public ListNode SortList(ListNode head) {
// check for empty or single element list
if (head == null || head.next == null)
{
return head;
}
// find the middle of the list
ListNode middle = FindMiddle(head);
// split the list into two halves
ListNode left = head;
ListNode right = middle.next;
middle.next = null;
// sort each half
left = SortList(left);
right = SortList(right);
// merge the sorted halves
return MergeLists(left, right);
}
private ListNode FindMiddle(ListNode head)
{
// slow and fast pointers to find the middle of the list
ListNode slow = head;
ListNode fast = head;
// 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;
}
}