# 725. Split Linked List in Parts 分隔链表

@TOC

## # 题目描述

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:

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

## # 题目大意

1.如果链表的长度比k小就用null来补充。 就如给的例1一样，链表长度为3但是k的值为5，所以将链表分为5段时，节点不够，所以后面的都用null来表示。

2.如果链表不能平均分的时候，各段相差的节点数不能超过1，并且前面分段的要比后面的长。 就如给的例2一样，链表长度为10，分为3段，此时不能平均分配，各段相差的不能超过1并且前面分段的要比后面的长，所以就分为三段：[1,2,3,4]、[5,6,7]、[8,9,10]。

3.最后将每段组成一个链表，然后全部装进数组中返回。

## # 解题方法

（1）商为0，余数为0。

（2）商为0，余数不为0。

（3）商不为0，余数为0。

（4）商不为0，余数不为0。

python代码如下：

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def splitListToParts(self, root, k):
"""
:type root: ListNode
:type k: int
:rtype: List[ListNode]
"""
nodes = []
counts = 0
each = root
while each:
counts += 1
each = each.next
num = counts / k
rem = counts % k
for i in range(k):
for j in range(num):
node = ListNode(root.val)
each.next = node
each = each.next
root = root.next
if rem and root:
rmnode = ListNode(root.val)
each.next = rmnode
if root:
root = root.next
rem -= 1
return nodes
``````

C++代码如下：

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k) {
int len = getLength(root);
int c = len / k; // each part num
int r = len % k; // remain
vector<ListNode*> res(k);
int pos = 0;
while (root) {
int curlen = r > 0 ? c + 1 : c;
--r;
res[pos] = root;
++pos;
root = cut(root, curlen);
}
return res;
}
int getLength(ListNode* root) {
int res = 0;
while (root) {
++res;
root = root->next;
}
return res;
}
// cut root, len = k, return k + 1
ListNode* cut(ListNode* root, int k) {
int count = 0;
ListNode* prev = nullptr;
while (count < k) {
prev = root;
root = root->next;
++count;
}
prev->next = nullptr;
return root;
}
};
``````

## # 日期

2018 年 3 月 13 日 2019 年 2 月 26 日 —— 二月就要完了