private ListNode mergeSort(ListNode head, int count) {
//        callTime++;
        if (head == null || head.next == null || count == 1) {
            return head;
        }

        int leftCount = count / 2;
        int rightCount = count - count / 2;
        int i = 1;
        ListNode leftTail = head;
        while (i++ < leftCount) {
            leftTail = leftTail.next;
        }
        ListNode originalRightHead = leftTail.next;
        leftTail.next = null;

        ListNode leftHead = mergeSort(head, leftCount);
        ListNode rightHead = mergeSort(originalRightHead, rightCount);

        // merge left and right
        ListNode lp = leftHead;
        ListNode rp = rightHead;
        
        ListNode sortedNode = null;
        if(lp.val < rp.val){
            sortedNode = lp;
            lp = lp.next;
        } else {
            sortedNode = rp;
            rp = rp.next;
        }

//        ListNode sortedNode = new ListNode(0);

        ListNode h = sortedNode;

        while (lp != null && rp != null) {
            if (lp.val < rp.val) {
                sortedNode.next = lp;
                lp = lp.next;
            } else {
                sortedNode.next = rp;
                rp = rp.next;
            }
            sortedNode = sortedNode.next;
        }
        if (lp == null) {
            sortedNode.next = rp;
        } else {
            sortedNode.next = lp;
        }
        return h;
    }