Sort List

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

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


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