Last updated on January 5th, 2025 at 11:56 pm
Here, we see a Split Linked List in Parts LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Linked List
Companies
Amazon
Level of Question
Medium
Split Linked List in Parts LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Linked List Manipulation”. This pattern involves traversing and modifying linked lists, often by splitting, merging, or reversing them.
3. Code Implementation in Different Languages
3.1 Split Linked List in Parts C++
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k) {
vector<ListNode*> parts(k, nullptr);
int len = 0;
for (ListNode* node = root; node; node = node->next)
len++;
int n = len / k, r = len % k;
ListNode* node = root, *prev = nullptr;
for (int i = 0; node && i < k; i++, r--) {
parts[i] = node;
for (int j = 0; j < n + (r > 0); j++) {
prev = node;
node = node->next;
}
prev->next = nullptr;
}
return parts;
}
};
3.2 Split Linked List in Parts Java
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] parts = new ListNode[k];
int len = 0;
ListNode node = root;
while (node != null) {
len++;
node = node.next;
}
int n = len / k, r = len % k;
node = root;
ListNode prev = null;
for (int i = 0; node != null && i < k; i++, r--) {
parts[i] = node;
for (int j = 0; j < n + (r > 0 ? 1 : 0); j++) {
prev = node;
node = node.next;
}
if (prev != null) {
prev.next = null;
}
}
return parts;
}
}
3.3 Split Linked List in Parts JavaScript
function ListNode(val, next) {
this.val = val;
this.next = next || null;
}
var splitListToParts = function(head, k) {
const parts = new Array(k).fill(null);
let len = 0;
let node = head;
while (node) {
len++;
node = node.next;
}
const n = Math.floor(len / k);
let r = len % k;
node = head;
let prev = null;
for (let i = 0; node && i < k; i++, r--) {
parts[i] = node;
for (let j = 0; j < n + (r > 0 ? 1 : 0); j++) {
prev = node;
node = node.next;
}
if (prev) {
prev.next = null;
}
}
return parts;
};
3.4 Split Linked List in Parts Python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def splitListToParts(self, head, k):
parts = [None] * k
len = 0
node = head
while node:
len += 1
node = node.next
n, r = divmod(len, k)
node = head
prev = None
for i in range(k):
parts[i] = node
for j in range(n + (1 if r > 0 else 0)):
prev = node
node = node.next
if prev:
prev.next = None
if r > 0:
r -= 1
return parts
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(k) |
| Java | O(n) | O(k) |
| JavaScript | O(n) | O(k) |
| Python | O(n) | O(k) |
- The code efficiently splits a linked list into
kparts, ensuring the firstrparts are slightly larger if the list cannot be evenly divided. - It uses two passes over the linked list: one to calculate the length and another to split the list.
- The algorithm is optimal in terms of time complexity (O(N)) and uses minimal additional space (O(k)).