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; } }