Leetcode Daily Question 08/09/2024 - 725. Split Linked List in Parts

Problem Description:

Given the head of a singly linked list and an integer k, 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 one. This may lead to some parts being null. The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later. Return an array of the k parts.

class ListNode:
  def __init__(self, val = 0, next = None):
    self.val = val
    self.next = next

from typing import Optional
class Solution:
  def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
    length = 0
    current = head
    while current:
      length += 1
      current = current.next
    
    each_length = length // k
    remainder = length % k
    
    result = [None] * k
    
    current = head
    prev = None
    for i in range(k):
      result[i] = current
      part_length = each_length + (1 if remainder > 0 else 0)
      for _ in range(part_length):
        prev = current
        current = current.next
      if prev:
        prev.next = None
      remainder -= 1
        
    return result

Explanation:

We want to split the linked list into k linked list as evenly as possible.

To do this, we first determine the length each part should have. We calculate the length of the whole linked list.

Then each part should have length of at least total length divided by k. Then we can distribute the remainder later when iterating through the linked list.

current = head
length = 0
while current:
  length += 1
  current = current.next

each_length = length // k
remainder = length % k

Our strategy to split the linked list is this.

Current will traverse the entirety of the original linked list to signify where the head of each linked list should be and prev will follow to terminate the individual linked lists.

We first initiate the result list with null nodes. This catches the cases where the total length is less than k. This also deals with the case where the original linked list is null.

result = [None] * k

prev = None
current = head
for i in range(k):
  result[i] = current # Current is the head of each individual linked list.
  part_length = each_length + (1 if remainder > 0 else 0) # Distribute the remainder.
  for _ in range(part_length):
    prev = current
    current = current.next
  
  if prev:
    prev.next = None # Terminates the individual linked list.
  
  remainder -= 1 # Decrement the remainder as we distribute it.

return result

The time complexity is O(n) as we need to traverse the entire linked list twice.

The space complexity is O(n) as we need to store the head of each linked list.

The full solution can be found near the top of the page.