LeetCode 725: Split Linked List in Parts

link

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: \mathcal{O}(n), space: \mathcal{O}(k).

# 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