Java one pass solution, O(N*k) -> O(N)


  • 0
    H
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode[] splitListToParts(ListNode root, int k) {
            Spliter s = new Spliter(k);
            ListNode temp;
            while(root != null) {
                temp = root;
                root = root.next;
                s.feed(temp);
            }
    
            return s.answer();
        }
        
        
        class Spliter {
            public Splitunit[] swapspace;
            
            public Spliter(int size) {
                swapspace = new Splitunit[size];
                for (int i = 0; i < size; i++) {
                    swapspace[i] = new Splitunit();
                }
            }
            
            public void feed(ListNode node) {
                int end = swapspace.length - 1;
                swapspace[end].append(node);
                for (int i = end; i >= 1; i--) {
                    if (swapspace[i].length > swapspace[i-1].length) {
                        swapspace[i-1].append(swapspace[i].decap());
                    }
                }
            }
            
            public ListNode[] answer() {
                ListNode[] ans = new ListNode[swapspace.length];
                for(int i = 0; i < swapspace.length; i++) {
                    ans[i] = swapspace[i].root;
                }
                return ans;
            }
            
            class Splitunit {
                int length;
                ListNode root;
                ListNode tail;
                
                public  ListNode decap() {
                    ListNode temp = root;
                    root = root.next;
                    length--;
                    return temp;
                }
                public  void append(ListNode node) {
                    if (length++ == 0) {
                        root = node;
                        tail = node;
                    } else {
                        tail.next = node;
                        tail = tail.next;
                    }
                    node.next = null;
    
                }
            }
        }
    }
    

Log in to reply
 

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