LeetCode.725.Split Linked List in Parts

---

题目描述

• 725 Split Linked List in Parts
  https://leetcode.com/problems/split-linked-list-in-parts/description/

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]
Example 1:

Input:  root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].

Example 2:

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

• The length of root will be in the range [0, 1000].
• Each value of a node in the input will be an integer in the range [0, 999].
• k will be an integer in the range [1, 50].

---

解题过程

这道题抽象出来就是序列中n个元素分成k组，每组元素个数尽量相等，即任意两组的元素个数之差不能大于1，且前面组的个数必须大于等于后面组的个数。
k小于n时
首先，不想那些细枝末节，n个元素均分成k组，每组的元素个数为[n/k]。
然后，考虑不能整除而且必须前面的个数大于后面的，所以我们从后往前安排，从后往前k-1组的元素个数都先定为 $\lfloor n/k \rfloor$ ，最后剩下的个数为 $n-(k-1)\lfloor n/k \rfloor$ ，如果都放到第1组的话肯定会太多，从而导致不满足任意两组个数之差小于等于1，那么怎么才能满足呢？每组最多放 $\lceil n/k \rceil$ 个的话肯定满足任意两组个数之差小于等于1，此外还得前面组个数大于等于后面组的个数，所以把剩余的个数依次从第1组开始往后放，使其元素个数增加到 $\lceil n/k \rceil$ 个，直到剩余的个数为0停止。
也就是，前 $n-k\lfloor n/k \rfloor$ 组的元素个数为 $\lfloor n/k \rfloor +1$ ，剩余组的元素个数为 $\lfloor n/k \rfloor$

AC后看Solution解析，才发现又想复杂了，其实很简单：前n%k组元素的个数是 $\lfloor n/k \rfloor +1$ ，剩余组的元素个数为 $\lfloor n/k \rfloor$。
唉！长时间没进行数学思考脑子就是不行，一些最基本的数学技巧都要想半天。

代码写起来有些繁琐，所以这道题不只是考数学逻辑，还考链表操作的熟练度，调试了好多次：

class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        //计算链表长度
        int linkedListLength=0;
        for(ListNode listNode = root; listNode != null; listNode=listNode.next){
            linkedListLength++;
        }

        //返回结果
        ListNode[] result = new ListNode[k];

        //k>n时，前n个是单节点链表，后面全为null
        if(k >= linkedListLength){
            int i=0;
            for(ListNode listNode = root; listNode != null; listNode=listNode.next){
                ListNode temp = new ListNode(listNode.val);
                result[i++] = temp;
            }
            while(i<k){
                result[i++] = null;
            }
        }else{//k<=n时
            int bigNum = linkedListLength - k * (int)Math.floor(linkedListLength/k);//前边的长段链表个数
            int bigSize = (int)Math.floor(linkedListLength/k) +1;//每个长段链表的size
            int littleNum = k - bigNum;//后边的短段链表的个数
            int littleSize = (int)Math.floor(linkedListLength/k);//短段链表的size
            int iterator=0;//返回结果的总迭代下标
            ListNode listNode = root;

            //生成bigNum个长段链表，放到结果数组中
            for(int i=0; i<bigNum; i++){
                ListNode prev = null;//此段链表的前驱结点
                for(int j=0; j<bigSize; listNode=listNode.next,j++){//往后走bigSize个结点
                    ListNode temp = new ListNode(listNode.val);
                    if(j==0){//此段链表的头结点放入结果数组
                        result[iterator++] = temp;
                    }else{
                        prev.next = temp;
                    }
                    prev = temp;
                }
            }

            //生成littleNum个短段链表，放到结果数组中
            for(int i=0; i<littleNum; i++){
                ListNode prev = null;//此段链表的前驱结点
                for(int j=0; j<littleSize; listNode=listNode.next,j++){//往后走littleSize个结点
                    ListNode temp = new ListNode(listNode.val);
                    if(j==0){//此段链表的头结点放入结果数组
                        result[iterator++] = temp;
                    }else{
                        prev.next = temp;
                    }
                    prev = temp;
                }
            }
        }
        return result;
    }
}

通过后看别人的代码，大体上有两种思路：一种是新生成链表，第二种是分割输入的链表。
我最喜欢的是下面的分割输入链表代码，真是简介漂亮通俗易懂，相比起来我的代码太臃肿了：

class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] parts = new ListNode[k];
        int len = 0;
        for (ListNode node = root; node != null; node = node.next)
            len++;
        // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
        int n = len / k, r = len % k;
        ListNode node = root, prev = null;
        for (int i = 0; node != null && i < k; i++, r--) {
            parts[i] = node;
            for (int j = 0; j < n + (r > 0 ? 1 : 0); j++) {
                prev = node;
                node = node.next;
            }
            prev.next = null;
        }
        return parts;
    }
}

里面涉及到的技巧：

remainder = N % k; //前remainder组元素个数较多1
result[i]元素个数为：N/k + (i < remainder ? 1 : 0), i = 0 ... k-1

---

GitHub代码

• leetcode-java / problems / _725_SplitLinkedListInParts /
  https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_725_SplitLinkedListInParts

---