Java solution with explanation


  • 0
    E

    The idea is to scan the list with a runner instance, splitting it into parts along the way.

    class Solution {
        public ListNode[] splitListToParts(ListNode root, int k) {
            List<ListNode> list = new ArrayList<>();
            
            // Find the length of the list
            int length = length(root);
            
            // Create a runner node, that will be used to split the list
            ListNode runner = new ListNode(-1);
            runner.next = root;
            
            while (k > 0 && runner != null) {
                // Find the length of current block/part
                int currBlockLen = length % k != 0 ? length / k + 1 : length / k;
                
                // Update the remaining length and the number of blocks/parts left
                length -= currBlockLen;
                k--;
                
                // Add the head of the current block to the result
                list.add(runner.next);
                
                // Detach the current block/part from the rest of the list
                while (currBlockLen-- > 0) runner = runner.next;
                ListNode end = runner;
                ListNode start = runner.next;
                end.next = null;
                runner = new ListNode(-1);
                runner.next = start;
            }
            
            // Populate the rest of the list with empty entries, if necessary
            while (k-- > 0) list.add(runner);
            
            // Return the result
            ListNode[] result = new ListNode[list.size()];
            return list.toArray(result);
        }
        
        
        // Finds list's length
        private int length(ListNode root) {
            int result = 0;
            while (root != null) {
                result++;
                root = root.next;
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.