链表面试问题

Question

所以问题是：

*给定一个具有头节点根的(单个(链表，编写一个函数将链表拆分为k个连续的链表"部分"。

每个部分的长度应尽可能相等：任何两个部分的尺寸差异都不应超过1。这可能会导致某些部分为空。

零件应按输入列表中出现的顺序排列，较早出现的零件的大小应始终大于或等于较晚出现的零件。

返回ListNode的列表，表示已形成的链表部分。*

我做了思考部分，得到ans[]的第一个索引应该有N%k+N/k节点，ans数组的后续部分应该有N/k节点。例如：

[1,2,3,4,5,6,7,8,9,10] k=3
ans = [ [1,2,3,4] [5,6,7] [8,9,10] ]

你可以看到ans[0]的长度为N%k+N/k=10%3+10/3=1+3=4，其余的长度为N/k=3

但我一直在努力调试我的代码，但我不确定它错在哪里。

public ListNode[] splitListToParts(ListNode root, int k) {
ListNode node = root;
int N=0;
while(node!=null){
N++;
node = node.next;
}
int intervalLen = N/k;
int start = N%k;
ListNode[] ans = new ListNode[k];
ListNode temp = root;
for(int z=0; z<start; z++){
System.out.println(temp.val);
temp = temp.next;
}
ans[0] = root;
ListNode nextNode = temp;
ListNode currNode = temp;
ListNode hold = root;
for(int i=0; i<k; i++){
if(i==0){
hold = root;
}else{
hold = nextNode;
}
for(int j=0; j<intervalLen-1;j++){
System.out.println(temp.val);
temp=temp.next;
}
nextNode = temp.next;//error here
currNode = temp;
currNode.next = null;
temp = nextNode;
ans[i] = hold;
}
return ans;
}

当我尝试打印时，它在4处给了我空指针异常，sys out，我将其作为输出

1, 2, 3, 4... error

所以我猜测4指向null，在下一个循环中，我们尝试执行nextNode=temp.next…nextNode=null.next，这会给出错误。。但我已经确保在代码中有下一个指针curr指针来避免这种情况，但仍然会发生这种情况，我不确定为什么会出现错误。

Answer 1

我在想这样的事情(解释为对代码的注释(；

public ListNode[] splitListToParts(ListNode root, int k) {
ListNode node = root;
int N=0;
while(node!=null){
N++;
node = node.next;
}
int intervalLen = N/k;
int start = N%k;
ListNode[] ans = new ListNode[k];
ListNode curr = root; // curr = current first element
for(int i=0; i<k; i++){
ans[i] = curr; // saving the current first element in the array
int elements = N / k; // elements is the number of elements to have in that array
/*
if the module give a number below the current element, increase elements.
let's take the example, + 1
[1,2,3,4,5,6,7,8,9,10,11] k=3
the answer is 
[1->2->3->4 , 5->6->7->8 , 9->10->11] right? so the module will return 11%3 = 2
and infact the 1st (index 0) and the 2nd (index 1) will have a + 1 element, and infact if 
i < 2 we are working on the first (index 0) or in the second (index 1)
*/
if(N%k < i) elements++; 
for(int j=0; j<elements;j++){ // just cicling on the values
System.out.println(temp.val);
curr=curr.next; // moving the current element to the next
}
ListNode tmp = curr; // saving the current element to a tmp variable
curr = curr.next; // moving the current one in order to have the right element at the beginning of the next cicle
tmp.next = NULL; // remove the pointer from the last element of this list to the first element of the next
}
return ans
}