题目

• 给定一个单链表并给定其头结点root,写一个函数实现将其分割为k个连续的链表
• 每一部分链表的长度要求：两个链表部分的长度不能超过1，某些链表可以置位空(null)
• 这些部分链表必须要按照输入链表的顺序，并且前一部分的长度必须大于等于后面部分的链表长度
• 返回一个分段链表头节点组成的数组
• 举例来说给定输入1->2->3->4， k = 5 返回[[1],[2],[3],[4],null]
• 给定root = [1, 2, 3], k = 5,返回[[1],[2],[3],[],[]]
• 给定root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3，返回Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

解题思路

• 首先，给定一个k，一个链表，假设链表长度为length,也即是我们要将链表分为k部分，且每两部分的长度不能超过1，那么按照正常的思想我们就是均分呗，那样就都是一样的
• 但是现在问题来了，我们均分之后即是length/k不能整除，也即是存在余数，此时余数remain=length % k, 既然不能超过1那么我们能做的只有取数组的前remain个数，分别将它的节点数再加1就可以完成我们的目标，有点类似于我们有10个硬币放进三个罐子，任意两个罐子之间的差值不能大于1，按照均分每个罐子3个硬币，此时还剩了一个硬币，再按照从头开始排放入第一个罐子形成4,3,3。如果是11个硬币就是形成4，4,3以此类推
• 在我们确定了平均值和average和remain之后就可以开始给数组装填数据了，数组中每个数对应的链表长度都应该是average或者average+1,形成一个数组的遍历
• 在数组遍历内部每次根据所需分段链表长度然后对链表进行遍历，将分段尾节点的next修改为null,head存入数组即可完成内循环，然后整体就完成了。

源代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] result = new ListNode[k];
        int count = 0;
        ListNode index = root;
        while (index != null) {
            count++;
            index = index.next;
        }
        int average = count/k;//平均的
        int remaining = count % k;//剩余的
        index = root;
        ListNode head = root;//每一段的头
        for (int i = 0; i < k; i++) {
            int total = i < remaining ? average + 1 : average;
            for (int j = 0; j < total - 1; j++) {   
                if (index != null) index = index.next;
            }
            result[i] = head;
            ListNode last = index;
            if (last != null) {
                index = index.next;
                head = index;
                last.next = null;
            } else head = null;
        }
        return result;
    }
}