Problem statement

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

Solution

Just do what is asked carefully: first, find number of nodes N in our list and evaluate d and r: how many times nodes there should be in the first part minus one. Then we can evaluate number of nodes in every part, using formula d + (i < r) - 1, where i goes from 0 to k-1. In each part, we do d (or d-1 steps), so now we are in the end of this part. If we are not at the None node (so, if part has at least one element), then we cut connection between current node and next one and go to the next node.

Complexity

Time complexity is O(n + k), because it can happen that k is much bigger than n. Space complexity is O(k) to write answer.

Code

class Solution:
    def splitListToParts(self, root, k):
        cur = root
        N = 0
        while cur:
            cur = cur.next
            N += 1
        d, r = divmod(N, k)

        ans = []
        cur = root
        for i in range(k):
            head = cur
            for j in range(d + (i < r) - 1):
                if cur: cur = cur.next
            if cur:
                cur.next, cur = None, cur.next
            ans.append(head)
        return ans