[Java/C++] Clean Code


  • 16

    Java

    class Solution {
        public ListNode[] splitListToParts(ListNode root, int k) {
            ListNode[] parts = new ListNode[k];
            int len = 0;
            for (ListNode node = root; node != null; node = node.next)
                len++;
            int n = len / k, r = len % k; // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
            ListNode node = root, prev = null;
            for (int i = 0; node != null && i < k; i++, r--) {
                parts[i] = node;
                for (int j = 0; j < n + (r > 0 ? 1 : 0); j++) {
                    prev = node;
                    node = node.next;
                }
                prev.next = null;
            }
            return parts;        
        }
    }
    

    C++

    class Solution {
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k) {
            vector<ListNode*> parts(k, nullptr);
            int len = 0;
            for (ListNode* node = root; node; node = node->next)
                len++;
            int n = len / k, r = len % k; // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
            ListNode* node = root, *prev = nullptr;
            for (int i = 0; node && i < k; i++, r--) {
                parts[i] = node;
                for (int j = 0; j < n + (r > 0); j++) {
                    prev = node;
                    node = node->next;
                }
                prev->next = nullptr;
            }
            return parts;
        }
    };
    

  • 0
    L

    Python O(n) solution using hash map

    class Solution(object):
        def splitListToParts(self, root, k):
            curr, numOfNodes, nodes = root, 0, {}
            while curr:
                nodes[numOfNodes] = curr # store node in hash map
                numOfNodes += 1
                curr = curr.next
    
            remain = numOfNodes % k
            ret, end = [], 0        
            for group in xrange(k):
                start = end
                end = start + numOfNodes // k
                if remain > 0: end, remain = end + 1, remain - 1
                if start in nodes:
                    ret.append(nodes[start])
                    nodes[end-1].next = None
                else: ret.append(None)
            return ret
    

Log in to reply
 

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