{x}
blog image

Split Linked List in Parts

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.

 

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

 

Constraints:

  • The number of nodes in the list is in the range [0, 1000].
  • 0 <= Node.val <= 1000
  • 1 <= k <= 50

Solution Explanation: Split Linked List in Parts

This problem involves splitting a singly linked list into k parts with lengths as equal as possible. The solution employs a straightforward approach that leverages integer division and the modulo operator to efficiently determine the size of each sublist.

Algorithm:

  1. Determine List Length: First, traverse the linked list to determine its total number of nodes (n).

  2. Calculate Sublist Sizes: Calculate the average sublist length (cnt) using integer division (n / k) and the remainder (mod) using the modulo operator (n % k). cnt represents the minimum length of each sublist, and mod indicates how many sublists will be one element longer than cnt.

  3. Split the List: Iterate k times. In each iteration:

    • Assign the current node (cur) as the head of the current sublist.
    • Calculate the length of the current sublist (m) as cnt plus 1 if the current iteration is less than mod (meaning this sublist gets an extra node).
    • Traverse m - 1 nodes to find the end of the current sublist.
    • Set the next pointer of the last node of the current sublist to null to separate it from the rest of the list.
    • Update cur to the node after the last node of the current sublist to start the next sublist.

  4. Return Sublists: Return an array of the k sublists (potentially including empty sublists if k is larger than the list length).

Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once to find its length and again to split it into sublists.

Space Complexity: O(k), where k is the number of parts. The space is used to store the array of sublist heads.

Code Implementation (Python):

# 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]]:
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        cnt, mod = divmod(n, k)
        ans = [None] * k
        cur = head
        for i in range(k):
            if cur is None:
                break
            ans[i] = cur
            m = cnt + int(i < mod)
            for _ in range(1, m):
                cur = cur.next
            nxt = cur.next
            cur.next = None
            cur = nxt
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, adapting the syntax and data structures accordingly. The core logic remains consistent across all implementations.