Split Linked List in Parts

https://leetcode.com/contest/weekly-contest-58/problems/split-linked-list-in-parts/

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list "parts".

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode's representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

Thoughts

分成k份, 不难想到遍历, 每len / k一切. 如果遍历点是在下个subset的头, 那需要一个prior; 如果是在上一个的尾, 则需要一个next, 否则切开后无法继续遍历. 有两种特殊情况 1. len < k 2. len % k != 0 对于第一种根据要求前面每份存一个, 剩下的清空. 对于第二种要求把余数平均分给前len % k个, 也就是前len % k个长度为len / k + 1.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private int size(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        res[0] = root;
        ListNode node = root, prior = null;
        int size = size(root);
        int len = size > k ? size / k : 1;
        int residual = size > k ? size % k : 0;
        int start = 0;
        for (; start < residual; start++) {
            res[start] = node;
            if (prior != null) {
                prior.next = null;
            }
            for (int j = 0; j <= len && node != null; j++) {
                prior = node;
                node = node.next;
            }
        }


        for (int i = start; i < k; i++) {
            res[i] = node;
            if (prior != null) {
                prior.next = null;
            }
            for (int j = 0; j < len && node != null; j++) {
                prior = node;
                node = node.next;
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(N), 空间O(1).