/*
     * Complete the function below.
     */
    /*
    For your reference:

    LinkedListNode {
        int val;
        LinkedListNode next;
    };
    */

    static LinkedListNode sort(int k, LinkedListNode head) {
        if (head == null)
            return null;

        LinkedListNode current = head;
        LinkedListNode next = null;
        int count = 1;

        while (current != null && count < k) {
            current = current.next;
            count++;
        }

        if (current != null) {
            next = current.next;
            current.next = null;
        } else
            next = null;

        //printList(head);
        head = mergeSort(head);

        LinkedListNode end = head;
        //printList(head);
        while (end != null && end.next != null) {
            end = end.next;
        }

        if (end != null)
            end.next = sort(k, next);

        return head;
    }

    static LinkedListNode sortedMerge(LinkedListNode a, LinkedListNode b) {
        LinkedListNode result = null;
        /* Base cases */
        if (a == null)
            return b;
        if (b == null)
            return a;

        /* Pick either a or b, and recur */
        if (a.val <= b.val) {
            result = a;
            result.next = sortedMerge(a.next, b);
        } else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }
        return result;

    }

    static LinkedListNode mergeSort(LinkedListNode h) {
        // Base case : if head is null
        if (h == null || h.next == null) {
            return h;
        }

        // get the middle of the list
        LinkedListNode middle = getMiddle(h);
        LinkedListNode nextofmiddle = middle.next;

        // set the next of middle node to null
        middle.next = null;

        // Apply mergeSort on left list
        LinkedListNode left = mergeSort(h);

        // Apply mergeSort on right list
        LinkedListNode right = mergeSort(nextofmiddle);

        // Merge the left and right lists
        LinkedListNode sortedlist = sortedMerge(left, right);
        return sortedlist;
    }

    // Utility function to get the middle of the linked list
    static LinkedListNode getMiddle(LinkedListNode h) {
        //Base case
        if (h == null)
            return h;
        LinkedListNode two = h.next;
        LinkedListNode one = h;

        // Move fastptr by two and slow ptr by one
        // Finally slowptr will point to middle node
        while (two != null) {
            two = two.next;
            if (two != null) {
                one = one.next;
                two = two.next;
            }
        }
        return one;
    }

    private static long ncr(int n, int k) {
        if (n == 0) return 1;
        if (k < n - k) k = n - k;
        long ans = 1;

        for (int i = 1; i <= k; i++) {
            ans *= (n - i + 1);
            ans /= i;
        }
        return ans;
    }