https://leetcode.com/problems/split-linked-list-in-parts/description/
initial
the v impot logic is that for a given length n, we can split into chunks right? Lets say we have n=10 and we wanna split into 2 chunks, each chunk will have 5 elements and no remainder. But if its n=10 and into 3 chunks, each chunk has 3 elements except there is a remainder of 1 which needs to be placed into a chunk. So it is 4,3,3.
logic is:
where k=number of chunks
chunk's number of elements = n/k
remainder = n%k
chunk's number of elements = n/k + (remainder>0 ? 1:0)
remainder--
lets see
sol
notice that part=number of elements in chunk. Notice the outer for loop, we are decrementing remainder as well cuz for each chunk we wanna decrement remainder.
ALSO very impt that we unlink the node at the end of each chunk. This is done by getting head pointer with prev variable in the inner for loop and setting its next to null.
divmod is useful to calc quotient and remainder
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
dummy=head
length=0
while dummy:
dummy=dummy.next
length+=1
q,r=divmod(length,k)
print(q,r)
ans=[None]*k
prev=None
tmp = head
for i in range(k):
ans[i]=tmp
for j in range(q+ (1 if r else 0)):
prev=tmp
tmp=tmp.next
if prev:
prev.next=None
if r:
r-=1
return ans complexity
n+k time
we store k number of list nodes so k space
