Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list "parts".

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1.  This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode's representing the linked list parts that are formed.


Examples
1->2->3->4, k = 5 // 5 equal parts
[ [1], 
[2],
[3],
[4],
null ]

Example 1:

Input: 
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].



Example 2:

Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.



Note:
The length of root will be in the range [0, 1000].
Each value of a node in the input will be an integer in the range [0, 999].
k will be an integer in the range [1, 50].

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        

Solutions:
# Definition for singly-linked list.
 # class ListNode(object):
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution(object):
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         if not root:
             return [None for _ in range(k)]
         
         if k == 1:
             return [root]
         
         count_nodes = 1
         start = root
         while start.next:
             start = start.next
             count_nodes += 1
         
         buckets = [0 for _ in range(k)]
         for i in range(len(buckets)):
             import math
             
             curr = math.ceil(count_nodes / k)
             count_nodes -= curr
             k -= 1
             buckets[i] = curr
             
             if count_nodes == 0:
                 break
 
         def split_ll(root, result, index, buckets):
             if index == len(buckets):
                 return
             if not root:
                 result.append(None)
                 return split_ll(root, result, index + 1, buckets)
             
             end = root
             curr_count = 1
             while curr_count < buckets[index]:
                 end = end.next
                 curr_count += 1
             
             start = root
             root = end.next
             end.next = None
             
             result.append(start)
             return split_ll(root, result, index + 1, buckets)
         
         result = []
         split_ll(root, result, 0, buckets)
         return result
             


# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         # Calculate length of linked list
         retList = []
         if root == None:
             for i in range(k):
                 retList.append([])
             return retList
         
         curr = root
         total_len = 1
         while(curr.next != None):
             curr = curr.next
             total_len += 1
         part_len = total_len // k
         r = total_len % k
         head = root
         prev = None
         for i in range(k):
            
             retList.append(head)
             if r>0:
                 inc = 1
             else:
                 inc = 0
             r -= 1
             for j in range(part_len+inc):
                 prev = head
                 head = head.next
             if prev:
                 prev.next = None
             
         return retList

# Definition for singly-linked list.
 # class ListNode(object):
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution(object):
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         if not root: return [None for _ in range(k)]
         length = 0;
         i = root;
         while i:
             i = i.next;
             length += 1;
             
         chunk_size = length//k
         num_longer_chunks = length % k
         
         res = [chunk_size + 1] * num_longer_chunks + [chunk_size] * (k - num_longer_chunks)
         
         curr = root;
         prev = None;
         
         for i,num in enumerate(res):
             res[i] = curr;
             for _ in range(num):
                 prev = curr;
                 curr = curr.next;
             
             prev.next = None;
             
         return res
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         length = 0
         cur_node = root
         while cur_node:
             length += 1
             cur_node = cur_node.next
         result = []
         part_base_len = length // k
         p1 = length % k
         p0 = k - p1
         cur_node = root
         for i in range(p1):
             head = None
             c_node = None
             for j in range(part_base_len + 1):
                 if not head:
                     head = ListNode(cur_node.val)
                     c_node = head
                 else:
                     c_node.next = ListNode(cur_node.val)
                     c_node = c_node.next
                 cur_node = cur_node.next
             result.append(head)
         for i in range(p0):
             if cur_node:
                 head = None
                 c_node = None
                 for j in range(part_base_len):
                     if cur_node:
                         if not head:
                             head = ListNode(cur_node.val)
                             c_node = head
                         else:
                             c_node.next = ListNode(cur_node.val)
                             c_node = c_node.next
                         cur_node = cur_node.next
                 result.append(head)
             else:
                 result.append([])
         return result

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         
         n = 0
         res = []
         def deepth(root):
             if root == None:
                 return 0
             if root.next == None:
                 return 1
             return 1 + deepth(root.next)
         n = deepth(root)
         if n <= k:
             for i in range(n):
                 res.append([root.val])
                 root = root.next
             for i in range(k-n):
                 res.append([])
         if n > k:
             j = [n//k]*k
             for i in range(n%k):
                 j[i] += 1
             for i in j:
                 temp = []
                 for k in range(i):
                     temp.append(root.val)
                     root = root.next
                 res.append(temp)
         return res

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         #先划分长度，在填充
         le=0#处理[]空树
         p=root
         #求长度
         while p:
             le+=1
             p=p.next
         #每个小段长度
         l=le//k
         r=le%k
         
         #填充
         res=[]
         pre=ListNode(0)
         head=root
         #k个小段
         for i in range(k):
             #root存在
             if head:
                 res.append(head)
                 r-=1
                 #每个小段里填充的元素数
                 for j in range(l+(r>=0)):
                     pre=head
                     head=head.next
                 #切断
                 pre.next=None
             else:
                 res.append(None)
         return res
         
             
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
 
         #先求长度，对长度划分
         lg=0
         p=root
         while p:
             lg+=1
             p=p.next
         #每个小序列的长度
         l=lg//k
         #分配r
         r=lg%k
         
         res=[]
         head=root
         pre=ListNode(0)
         for i in range(k):
             if head:
                 r-=1
                 res.append(head)
                 for j in range(l+(r>=0)):
                     print(22)
                     pre=head
                     head=head.next
                 pre.next=None
                 print(111)
             else:
                 res.append(None)
             
         return res
         
             
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         '''
         total = 0
         nums = list()
         head = root
         while head:
             total += 1
             nums.append(head.val)
             head = head.next
         
         if total%k == 0:
             size = max(total//k, 1)
             total = k * size
             res = list()
             for i in range(0, total, size):
                 tmp = nums[i: i+size]
                 if not tmp:
                     tmp = []
                 res.append(tmp)
             return res
         else:
             len1 = total%k
             len2 = k - len1
             size1 = max(math.ceil(total/k), 1)
             size2 = max(total//k, 1)
             total1 = size1 * len1
             total2 = size2 * len2
             res1 = list()
             res2 = list()
             for i in range(0, total1, size1):
                 tmp = nums[i: i+size1]
                 if not tmp:
                     tmp = []
                 res1.append(tmp)
             #print('0', total1, size1, res1)
             for i in range(total1, total1+total2, size2):
                 tmp = nums[i: i+size2]
                 if not tmp:
                     tmp = []
                 res2.append(tmp)
             #print(total1, total, size2, res2)
             return res1+res2
         '''
         total = 0
         head = root
         while head:
             total += 1
             head = head.next
         head = root
         size = total//k
         remain = total%k
         res = list()
         for i in range(k):
             tmp = list()
             for j in range(size):
                 try:
                     tmp.append(head.val)
                     head = head.next
                 except:
                     continue
             if remain > 0:
                 try:
                     tmp.append(head.val)
                     head = head.next
                 except:
                     continue
                 remain -= 1
             res.append(tmp)
         return res


# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         res=[]
         ans=[]
         for i in range(k):
             res.append([])
         while root:
             ans.append(root.val)
             root=root.next
             
         l=len(ans)
         l1=l//k
         l2=l%k
         print(l1,l2)
         for i in range(k):
             if l2>0:
                 for j in range(l1+1):
                     res[i].append(ans.pop(0))
             else:
                 for j in range(l1):
                     res[i].append(ans.pop(0))
             print(res)
             l2-=1
         return res
             

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         def list_len(head):
             cnt = 0
             while head:
                 cnt += 1
                 head = head.next
             return cnt
         
         tlen = list_len(root)
         res = [None] * k
         if tlen <= k:
             i = 0
             head = root
             while head:
                 res[i] = head
                 i += 1
                 pre = head
                 head = head.next
                 pre.next = None
             return res
         
         rich = tlen % k
         h = tlen // k
         # print(tlen, k , rich, h)
         res[0] = root
 
         head = root
         cur = 1
         while cur < k:
             i = 1
             while i < h:
                 head = head.next
                 i += 1
             if rich > 0:
                 head = head.next
                 rich -= 1
             pre = head
             head = head.next
             res[cur] = head
             pre.next = None
             cur += 1
         return res
             
             
             
         
         
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 import math
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         def length(node):
             result = 0
             while node is not None:
                 result += 1
                 node = node.next
             return result
         
         total = length(root)
         result = []
         current = root
         
         while k > 0:
             l = math.ceil(total / k)
             total -= l
             k -= 1
             
             if l == 0:
                 result.append(None)
                 continue
                 
             root = current
             for _ in range(l-1):
                 current = current.next
             result.append(root)
             current.next, current = None, current.next
             
         return result

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """    
         # get the length of list:
         node = root
         total = 0
         while node:
           total += 1
           node = node.next
 
         avg = int(total / k)
         extras = total % k
         result = [None] * k
         
         curr = root
         for i in range(k):
           result[i] = curr
           if extras > 0:
             steps = avg + 1
             extras -= 1
           else:
             steps = avg
           prev = None
           for j in range(steps):
             prev = curr
             curr = curr.next
           
           if prev:
             prev.next = None
         
         return result
 
             
             
         
         
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         count = 0
         node = root
         while node:
             count += 1
             node = node.next
         baseNodeLen = int(count / k)
         extraLenCount = count % k
         ans = []
         newRoot = root
         for index in range(k):
             if newRoot == None:
                 ans.append(None)
                 continue
             currentLen = baseNodeLen
             lastNode = newRoot
             if extraLenCount > 0:
                 currentLen += 1
                 extraLenCount -= 1
             for i in range(currentLen - 1):
                 lastNode = lastNode.next
             currentRoot = newRoot
             newRoot = lastNode.next
             lastNode.next = None
             ans.append(currentRoot)
         return ans

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def splitListToParts(self, root, k):
         """
         :type root: ListNode
         :type k: int
         :rtype: List[ListNode]
         """
         ans = []
         rootLength = self.length(root)
         width, reminder = divmod(rootLength,k)
         curr = root
         for i in range(k):
             head = curr
             for j in range(width + (i<reminder) -1):
                 if curr: curr = curr.next
             if curr:
                 pre = curr
                 curr = curr.next
                 pre.next = None
             ans.append(head)
         return ans
 
 
 
 
 
 
     def length(self, head):
         length = 0
         while head:
             length +=1
             head = head.next
         return length