725. Split Linked List in Parts - Medium

前往題目

想法

• 沒想到如何處理前面需要補上的部分

思路

1. 得到list總長度
2. 利用除法以及取餘得到最少要多少個元素在一個part，然後需要補多少個
3. 開始建造part，如果有需要補的也要加上去，一次補一個(題目規定)
4. 建造完一個part就把尾巴斷開，補上null

很多條件需要考慮…

Code

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] res = new ListNode[k];
        ListNode cur = head;
        int len = 0;

        // Obtain the length
        while (cur != null) {
            cur = cur.next;
            ++len;
        }

        int baseLen = len / k; // Min. element of a part
        int remainder = len % k; // Number of element should be put in the first part
        cur = head;

        // Build all the parts
        for (int i = 0; i < k; ++i) {
            // Init. a part
            res[i] = cur;

            // Build a part
            for (int j = 0; j < baseLen - 1 + (remainder > 0 ? 1 : 0); ++j) {
                if (cur == null)
                    break;
                cur = cur.next;
            }
            // No two parts should have a size differing by more than one
            remainder = remainder > 0 ? remainder - 1 : remainder;
            // Break the tail, set cur for the next part
            if (cur != null) {
                ListNode next = cur.next;
                cur.next = null;
                cur = next;
            }

        }
        return res;
    }
}