public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
             return head;
        }
        ListNode h1 = head;
        ListNode d1 = new ListNode(0);
        d1.next = head;
        ListNode p = head, pp = d1;
        while(p != null && p.next != null){
            pp = pp.next;
            p = p.next.next;
        }

        ListNode tmp = pp.next;
        pp.next = null;
        pp = tmp;

        ListNode h2 = pp;
        ListNode h1Sorted = sortList(h1);
        ListNode h2Sorted = sortList(h2);

        ListNode dummy1 = new ListNode(0);
        ListNode p1 = dummy1;
        ListNode p2 = h2Sorted;

        dummy1.next = h1Sorted;

        while(p1.next != null && p2 != null){
            if(p2.val <= p1.next.val){
                tmp = p2;
                p2 = p2.next;
                tmp.next = p1.next;
                p1.next = tmp;
            }else{
                p1 = p1.next;
            }
        }

        if(p1.next == null){
            p1.next = p2;
        }

        return dummy1.next;
    }