725. 分隔链表

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {

    private int count(ListNode head) {
        int ans = 0;
        ListNode cur = head;
        while (cur != null) {
            ans++;
            cur = cur.next;
        }
        return ans;
    }

    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] ans = new ListNode[k];
        int count = count(head);
        int add = count % k;
        int num = count / k;

        int index = 0;
        int cnt = 0;
        int need = num + (index < add ? 1 : 0);

        ListNode left = head;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cnt++;
            if (cnt == need) {
                ans[index++] = left;
                cur.next = null;
                left = next;
                need = num + (index < add ? 1 : 0);
                cnt = 0;
            }
            cur = next;
        }


        return ans;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}