Approach #1: Create New Lists [Accepted]

Intuition and Algorithm

If there are nodes in the linked list root, then there are items in each part, plus the first parts have an extra item. We can count with a simple loop.

Now for each part, we have calculated how many nodes that part will have: width + (i < remainder ? 1 : 0). We create a new list and write the part to that list.

Our solution showcases constructs of the form a = b = c. Note that this syntax behaves differently for different languages.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the given list. If is large, it could still require creating many new empty lists.

  • Space Complexity: , the space used in writing the answer.


Approach #2: Split Input List [Accepted]

Intuition and Algorithm

As in Approach #1, we know the size of each part. Instead of creating new lists, we will split the input list directly and return a list of pointers to nodes in the original list as appropriate.

Our solution proceeds similarly. For a part of size L = width + (i < remainder ? 1 : 0), instead of stepping L times, we will step L-1 times, and our final time will also sever the link between the last node from the previous part and the first node from the next part.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the given list. If is large, it could still require creating many new empty lists.

  • Space Complexity: , the additional space used in writing the answer.


Analysis written by: @awice.