本题的关键是如何分割;
若已知单链表长度为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;}
}