First we find the expected group sizes from the length of the list and k and then copy the heads of the groups as we do a second pass.
Time: , space:
.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def get_next_group(self, head, size):
prev, curr = None, head
while curr and size > 0:
prev = curr
curr = curr.next
size -= 1
if prev:
prev.next = None
return curr
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
list_len = 0
t = head
while t:
list_len += 1
t = t.next
q, r = divmod(list_len, k)
sizes = [q] * k
for i in range(k):
if r == 0:
break
sizes[i] += 1
r -= 1
sublists = []
curr_head = head
for sz in sizes:
next_head = self.get_next_group(curr_head, sz)
sublists.append(curr_head)
curr_head = next_head
return sublists
Leave a comment