725. Split Linked List in Parts

本题的关键是如何分割；

若已知单链表长度为n，要分成k部分
则，每部分至少有 n/k个结点；前n%k个结点有n/k+1个节点

/*** 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 p = root;int n = 0;//记录单链表root的总长度while(p!=null){
    p = p.next;n++;}p = root;int a = n/k, b = n%k;//a表示分割为a个部分，b表示前b个部分要多加上一个结点ListNode []ans = new ListNode[k];//创建k个ListNode类型的对象引用for(int i = 0;i<k;i++){
    ListNode head  = new ListNode(0);ListNode p1 = head;for(int j = 0;j< a+(i<b? 1:0);j++){
    p1.next = new ListNode(p.val);p1 = p1.next;p = p.next;}ans[i] = head.next;}return ans;}
}

更优解：（待阅读）

/*** 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) {
    int N = 0;ListNode cur = root;while (cur != null) {
    N++;cur = cur.next;}int mod = N % k;int size = N / k;ListNode[] ret = new ListNode[k];cur = root;for (int i = 0; cur != null && i < k; i++) {
    ret[i] = cur;int curSize = size + (mod-- > 0 ? 1 : 0);for (int j = 0; j < curSize - 1; j++) {
    cur = cur.next;}ListNode next = cur.next;cur.next = null;cur = next;}return ret;}
}