Approach #2: It can be O(n) time and O(1) extra space (apart from ListNode[]) - 5ms.


  • 0
    S
    
    class Solution {
        public ListNode[] splitListToParts(ListNode root, int k) {
    
            ListNode[] list = new ListNode[k];
    
            int totalNodes =0;
            ListNode current = root;
            while(current !=null){
                totalNodes++;
                current = current.next;
            }
            
            int minNumOfNodesInEachGroup = totalNodes/k;
            int extraNodesInNGroup = totalNodes%k;        
            
            current = root;
            int index =0;
    
            while(index <k){
                
                list[index] = current;
                int count = minNumOfNodesInEachGroup + (index < extraNodesInNGroup ? 1 : 0);
                int temp = 1 ;
                
                while(current !=null && temp<count){
                    current = current.next;
                    temp++;
                }
                
                if(current ==null) break; //make sure it's O(n)
                
                ListNode newCurrent = current.next;
                current.next = null;
                current = newCurrent;
                index++;
            }
            
            return list;
        }
    }
    

Log in to reply
 

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