/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    public ListNode sortList(ListNode head) {

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

            return head;

        int size = 1;

        ListNode start = new ListNode(0);

        start.next = head;

        while( true ){

            ListNode node1 = start;

            ListNode node2 = start.next;

            for( int i = 0 ; i < size && node2!=null;i++){

                node2 = node2.next;

            }

            if( node2 == null )

                break;

            ListNode nnn = start.next;

            while( node2 != null ){

                node1 = helper(node1,node2,size);

                if( node1 == null  )

                    break;

                node2 = node1.next;

                for( int i = 0 ; i< size && node2 != null;i++){

                    node2 = node2.next;

                }

            }

            size*=2;

        }

        return start.next;

    }

    public ListNode helper(ListNode node1,ListNode node2,int size){

        int num1 = 0,num2 = 0;

        ListNode node = null;

        if( node1.next.val < node2.val ){

            node = node1.next;

            node1 = node1.next.next;

            num1++;

        }else{

            ListNode nn = node1.next;

            node1.next = node2;

            node1 = nn;

            node = node2;

            node2 = node2.next;

            num2++;

        }

        while( num1 < size && num2 < size && node1 != null && node2 != null){

            if( node1.val < node2.val ){

                node.next = node1;

                node = node1;

                node1 = node1.next;

                num1++;

            }else{

                node.next = node2;

                node = node2;

                node2 = node2.next;

                num2++;

            }

        }

        while( num1 < size && node1 != null){

            node.next = node1;

            node = node1;

            node1 = node1.next;

            num1++;

        }

        while( num2 < size && node2 != null){

            node.next = node2;

            node = node2;

            node2 = node2.next;

            num2++;

        }

        node.next = node2;

        return node;

    }

}