java - 链表面试题

Question

所以问题是:

*给定一个带有头节点 root 的(单)链表，编写一个函数将该链表拆分为 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
}