Solution For Split Linked List In Parts

Problem statement:

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

Each of the linked list parts 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.

Solution:

The given problem can be solved by traversing through the linked list and calculating its length. The length of the linked list is divided by the value of k to find the number of nodes to be present in each part. We also find the remaining nodes that are left after all parts have equal nodes.

We then create a new array of k-linked lists and assign each part its respective nodes. We use the remaining variable to assign the remaining nodes to the first k%nodes will get the remaining nodes since we assign nodes in a round-robin fashion starting from the first partition.

Algorithm:

1. Determine the length of the Linked List_list. The length of the linked list is count.
2. Determine the quotient and remainder from count divided by k.
3. Initialize an empty array result with k linked lists.
4. Initialize a pointer current to head.
5. For i = 0 to k-1:
6. Define size as the quotient of the count of the linked list divided by k.
7. If the remainder is greater than 0, subtract 1 from the remaining variable.
8. Add size nodes from current to result[i].
9. Update the current pointer such that it points to the next node of the last node added to the result[i].
10. Decrease remaining by 1 if it is greater than 0.
11. Repeat Step 8-10 until all linked lists have been divided.
12. Return result.

Python Code:

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

def splitListToParts(head: ListNode, k: int):
# initialize count and current variables
count = 0

``````# calculate the length of the linked list
while current:
count += 1
current = current.next

# calculate size and remaining
size, remaining = divmod(count, k)

# initialize an empty array of k linked lists
result = [None] * k

# set current pointer back to the head

# assign nodes to each partition
for i in range(k):
result[i] = current

# add size nodes to the partition
for j in range(size + (i < remaining) - 1):
if current:
current = current.next

# store the next node after the partition in the curr variable
if current:
curr = current.next

# break the linked list
current.next = None
current = curr

# return result list of partitions
return result
``````

Time Complexity:

The algorithm has a time complexity of O(n), where n is the number of nodes in the Linked List. Traverse the entire Linked List once to find out its length, then once again to divide it into partitions. Both operations have a linear time complexity. The overall time complexity is O(n).

Sapce Complexity:

We allocate k number of linked lists in the result list. Besides, we use additional pointers and variables, and their space usage does not depend on the linked list size or k. The overall space complexity is O(k).

Step by Step Implementation For Split Linked List In Parts

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
// base case
if (root == null) {
return new ListNode[k];
}

// get the length of the list
int len = 0;
ListNode curr = root;
while (curr != null) {
curr = curr.next;
len++;
}

// calculate the size of each sublist
int sublistSize = len / k;
int remainder = len % k;

// create an array to store the sublists
ListNode[] sublists = new ListNode[k];

// initialize the first sublist
curr = root;
sublists[0] = curr;

// create the remaining sublists
for (int i = 1; i < k; i++) {
// if there is a remainder, add one to the size of the sublist
int size = sublistSize;
if (remainder > 0) {
size++;
remainder--;
}

// create the sublist
for (int j = 0; j < size - 1; j++) {
curr = curr.next;
}
sublists[i] = curr.next;
curr.next = null;
curr = sublists[i];
}

return sublists;
}
}```
```# 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, root: ListNode, k: int) -> List[ListNode]:
# Base case
if not root:
return [None] * k

# Get the length of the list
curr, length = root, 0
while curr:
curr, length = curr.next, length + 1

# Split the list into k parts
part_length, longer_parts = divmod(length, k)
output = [part_length + 1] * longer_parts + [part_length] * (k - longer_parts)

# Split the list
curr, prev = root, None
for index, num in enumerate(output):
output[index] = curr
for i in range(num):
prev, curr = curr, curr.next
if prev:
prev.next = None

return output```
```/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} root
* @param {number} k
* @return {ListNode[]}
*/
var splitListToParts = function(root, k) {
// create an array of k elements
const result = new Array(k).fill(null);

// base case: if root is null, return the array of k elements
if (!root) {
return result;
}

// get the length of the list
let length = 0;
let curr = root;
while (curr) {
length++;
curr = curr.next;
}

// get the number of elements in each sublist
let num = length / k;
let rem = length % k;

// create each sublist
curr = root;
for (let i = 0; i < k; i++) {
// create a new list
const list = new ListNode(null);
let temp = list;

// add num elements to the sublist
for (let j = 0; j < num; j++) {
temp.next = new ListNode(curr.val);
curr = curr.next;
temp = temp.next;
}

// add an extra element to the sublist if there are any remaining elements
if (rem > 0) {
temp.next = new ListNode(curr.val);
curr = curr.next;
rem--;
}

// add the sublist to the result array
result[i] = list.next;
}

return result;
};```
```/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector splitListToParts(ListNode* root, int k) {
// Your code here
vector parts(k, nullptr);
int len = 0;
for (ListNode* node = root; node; node = node->next)
len++;
int n = len / k, r = len % k; // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
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;
}
};```
```/**
* Definition for singly-linked list.
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode[] SplitListToParts(ListNode root, int k) {
// create an array of ListNodes of size k
ListNode[] parts = new ListNode[k];

// if the input linked list is null, return the array of ListNodes
if (root == null) {
return parts;
}

// get the length of the input linked list
int length = 0;
ListNode current = root;
while (current != null) {
length++;
current = current.next;
}

// calculate the size of each sublist
int sublistSize = length / k;
int remainder = length % k;

// create each sublist
current = root;
for (int i = 0; i < k; i++) {
parts[i] = current;
// if there is a remainder and we are on the first few sublists, add one to the sublist size
int currentSublistSize = sublistSize + (remainder > 0 ? 1 : 0);
// reduce the remainder by one, if it is greater than 0
if (remainder > 0) {
remainder--;
}
// create the sublist by iterating through the current list and setting the next pointer to null after the sublist size is reached
for (int j = 0; j < currentSublistSize - 1; j++) {
if (current != null) {
current = current.next;
}
}
// if we are not at the end of the list, set the next pointer of the last node in the sublist to null and update the current node to the next node in the list
if (current != null) {
ListNode next = current.next;
current.next = null;
current = next;
}
}
return parts;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]