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:
[0, 1000].0 <= Node.val <= 10001 <= k <= 50This approach involves two main steps. First, traverse the linked list to determine its length. Then, decide how to split this length evenly across the k parts. Calculate the base size for each part and determine how many parts need an extra node.
The solution first calculates the total length of the linked list. Using this information, it determines the base size that each part should have and how many of the initial parts should receive an extra node due to the remainder from the division of length by k. It then iterates through the linked list, splitting it into the desired parts by adjusting the next pointers appropriately.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list parts.
This approach involves iterating through the linked list and modifying the pointers to split the list directly into parts of calculated sizes based on total length and k. It ensures that the list splitting does not require additional passes, combining calculation and splitting in a single traversal.
This C solution simplifies the approach by combining the length calculation and direct list splitting into one step. By iterating and breaking the list dynamically, this technique ensures efficiency in handling the linked list pointers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list pointers.
| Approach | Complexity |
|---|---|
| Calculate Length and Split | Time Complexity: O(n) where n is the length of the linked list. |
| Iterative Splitting with Modification | Time Complexity: O(n) where n is the length of the linked list. |
Split Linked List in Parts - Leetcode 725 - Python • NeetCodeIO • 13,778 views views
Watch 9 more video solutions →Practice Split Linked List in Parts with our built-in code editor and test cases.
Practice on FleetCode