Split Linked List In Parts

---

Intuition

• The important aspect of this problem is that you have to amortize the cost such that each grouping of the k groups differs by at most one, with the left side groups having the extra elements.
• If k is more than n, you leave the n - k slots after n blank
• Make a HashMap that stores each of the n nodes. This will allow you set the correct node and cut off the previous grouping through hm[n - 1].next = None.
• Notice that when k < n, there are n // k groupings, and n % k leftover. You will amortize the leftover by adding one extra element until everything left over is gone.

Complexity

Runtime

$O(N)$ due to looping through all elements twice.

Space

$O(N)$ due to the hashmap and res array.

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, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        res = [None for _ in range(k)]
        if not head:
            return res
 
        hm = {}
        n = 0
        itr = head
        while itr:
            hm[n] = itr
            n += 1
            itr = itr.next
        
        res[0] = head
 
        k = min(n, k)
        c = 1
        space, leftover = divmod(n, k)
 
        i = space
        while i < n:
            if leftover:
                i += 1
                leftover -= 1
                
            hm[i - 1].next = None
            res[c] = hm[i]
            c += 1
            i += space
 
        return res

Notes

Cards

START Basic Front: Split Linked List In Parts Back: Ammortise the n // k groups by adding one of the leftover n % k elements per grouping END

---

References

• Split Linked List In Parts