1
# Runtime: 50 ms (Top 81.38%) | Memory: 14.5 MB (Top 12.03%)
2
# Definition for singly-linked list.
3
# class ListNode:
4
# def __init__(self, val=0, next=None):
5
# self.val = val
6
# self.next = next
7
class Solution:
8
    def splitListToParts(
9
        self, head: Optional[ListNode], k: int
10
    ) -> List[Optional[ListNode]]:
11
        length = 0
12
        cur = head
13
        while cur:
14
            length += 1
15
            cur = cur.next
16
        # DON'T do following since this makes head become null
17
        # while head:
18
        # length += 1
19
        # head = head.next
20

21
        # calculate the base size and the number of parts contain extra number
22
        size, extra = length // k, length % k
23

24
        # create empty list to store split parts
25
        res = [[] for _ in range(k)]
26

27
        # use two ptrs to split parts
28
        prev, cur = None, head
29

30
        for i in range(k):
31
            res[i] = cur
32
            # if this part contains extra number, it has (size+1) number
33
            for j in range(size + (1 if extra > 0 else 0)):
34
                prev, cur = cur, cur.next
35
            if prev:
36
                prev.next = None
37
            extra -= 1
38

39
        return res