Sort Linked List Problem LeetCode

 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]

Example 3:

Input: head = []

Output: []

 

Constraints:

The number of nodes in the list is in the range [0, 5 * 104].

-105 <= Node.val <= 105

 

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

/**

 * 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) {

        if(head ==null || head.next ==null)

        {

            return head;

        }

        ListNode middle=getMiddle(head);

        ListNode leftright=middle.next;

        middle.next=null;

        ListNode left=sortList(head);

        ListNode right=sortList(head);

       return  merge(left,right);

       

    }

    public static ListNode getMiddle(ListNode head)

    {

        if(head==null)return head;

        ListNode fast=head;

        ListNode slow=head;

        while(fast.next !=null && fast.next.next !=null)

        {

            fast=fast.next.next;

            slow=slow.next;

        }

        return slow;

    }

    public static ListNode merge(ListNode left,ListNode right)

    {

        if(left ==null)return right;

        if(right==null) return left;

        ListNode result;

     if(left.val <= right.val)

     {

        result=left;

        result.next=merge(left.next,right);

     }

     else

     {

        result=right;

        result.next=merge(left,right.next);

     }

     return result;

    }

}