# Split Linked List in Parts

[https://leetcode.com/contest/weekly-contest-58/problems/split-linked-list-in-parts/](https://leetcode.com/contest/weekly-contest-58/problems/split-linked-list-in-parts/)

> 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 ]

## Thoughts

分成k份, 不难想到遍历, 每len / k一切. 如果遍历点是在下个subset的头, 那需要一个prior; 如果是在上一个的尾, 则需要一个next, 否则切开后无法继续遍历. 有两种特殊情况 1. len < k 2. len % k != 0 对于第一种根据要求前面每份存一个, 剩下的清空. 对于第二种要求把余数平均分给前len % k个, 也就是前len % k个长度为len / k + 1.

## Code

```
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private int size(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        res[0] = root;
        ListNode node = root, prior = null;
        int size = size(root);
        int len = size > k ? size / k : 1;
        int residual = size > k ? size % k : 0;
        int start = 0;
        for (; start < residual; start++) {
            res[start] = node;
            if (prior != null) {
                prior.next = null;
            }
            for (int j = 0; j <= len && node != null; j++) {
                prior = node;
                node = node.next;
            }
        }


        for (int i = start; i < k; i++) {
            res[i] = node;
            if (prior != null) {
                prior.next = null;
            }
            for (int j = 0; j < len && node != null; j++) {
                prior = node;
                node = node.next;
            }
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(N), 空间O(1).
