class Solution {
    public int getNextPartLen(int left, int k) {
        return (int) Math.ceil((float) left / k);
    }

    public int getLen(ListNode head) {
        if (head == null) return 0;
        return 1 + getLen(head.next);
    }

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        int len = getLen(root);
        ListNode start = root;
        int cur = 0;
        while (cur < k) {
            int part = getNextPartLen(len, k - cur);
            if (start == null) {
                res[cur] = start;
            } else {
                // 找到尾巴，剪断，并更新下一个头结点
                // 此时保证一定可以遍历 part 次
                ListNode end = start;
                int m = 1;
                while (m < part) {
                    end = end.next;
                    m += 1;
                }
                res[cur] = start;
                start = end.next;
                end.next = null;
            }
            cur += 1;
            len -= part;
        }
        return res;
    }
}