图解leetcode725. 分隔链表

图解leetcode725. 分隔链表

1.题目描述：

给你一个头结点为head的单链表和一个整数k，请你设计一个算法将链表分隔为k个连续的部分。每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过1。这可能会导致有些部分为null。这k个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。返回一个由上述k部分组成的数组。

2.解题思路：

这道题有两个难点：①找出分割链表的方法；②将分割后的各个小链表以数组的形式返回。第一个问题分割链表的形式较容易能想到，对k取模和取余，取余所得的值按1分配到k取模所得的计数上。第二个问题，分割链表我考虑到使用栈，一次d出对应的个数，但是要注意每次第一个d出的值需要将其next置为null，断开链表。文字可能较难理解，看图解。

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] res = new ListNode[k];
        int count = 0;
        ListNode temp = head;
        while(temp != null){
            count++;
            temp = temp.next;
        }
        int a = count / k;
        int b = count % k;
        ListNode temp2 = head;
        Deque stack = new linkedList<>();
        while(temp2 != null){
            stack.push(temp2);
            temp2 = temp2.next;
        }
        int num = 0;
        ListNode temp3 = null;
        for(int j = k - 1;j >= 0;j--){
            num = 0;
            while(num < a && j >= b){
                temp3 = stack.pop();
                if(num == 0) temp3.next = null; 
                num++; 
            }
            while(num < a + 1 && j < b){
                temp3 = stack.pop();
                if(num == 0) temp3.next = null; 
                num++; 
            }
            res[j] = temp3;
        }
        return res;
    }
}

3.官方解法：思路差不多，但无需使用栈，代码也比较简单，空间复杂度O(1)。

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;
        ListNode temp = head;
        while (temp != null) {
            n++;
            temp = temp.next;
        }
        int quotient = n / k, remainder = n % k;
        ListNode[] parts = new ListNode[k];
        ListNode curr = head;
        ListNode currNext = null;//用来记录断掉链表的下一个节点
        for (int i = 0; i < k && curr != null; i++) {//curr != null防止类似示例1出现空指针异常
            parts[i] = curr;
            int partSize = quotient + (i < remainder ? 1 : 0);//用于找到需要断掉的节点
            for (int j = 1; j < partSize; j++) {
                curr = curr.next;
            }
            currNext = curr.next;
            curr.next = null;
            curr = currNext;
        }
        return parts;
    }
}