Day 32.2.txt

148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

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

 

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


/**
 * 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 {
    static int a[];
    public ListNode sortList(ListNode head) {
        if(head==null)
            return null;
        ListNode ptr;
        int c=0,i;
        for(ptr=head;ptr!=null;ptr=ptr.next)
        {
            c++;
        }
        a=new int[c];
        for(i=0,ptr=head;ptr!=null;ptr=ptr.next,i++)
        {
            a[i]=ptr.val;
        }
        task(a,0,i-1);
        for(i=0,ptr=head;ptr!=null;ptr=ptr.next,i++)
        {
            ptr.val=a[i];
        }
        return head;
    }
    void task(int n[] , int i , int j)
    {
        if(i<j)
        {
            int m=(i+j)/2;
            task(n,i,m);
            task(n,m+1,j);
            task1(n,i,m,j);
        }
    }
    void task1(int n[] , int s , int m , int e)
    {
        int b[]=new int[e-s+1];
        int i,j,k=0;
        i=s;
        j=m+1;
        while(i<=m&&j<=e)
        {
            if(n[j]>=n[i])
            {
                b[k++]=n[i];
                i++;
            }
            else
            {
                b[k++]=n[j];
                j++;
            }
        }
        while(i<=m)
        {
            b[k++]=n[i++];
        }
        while(j<=e)
        {
            b[k++]=n[j++];
        }
        for(i=s;i<=e;i++)
        {
            a[i]=b[i-s];
        }
    }
}