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:
- Determine the length of the Linked List_list. The length of the linked list is count.
- Determine the quotient and remainder from count divided by k.
- Initialize an empty array result with k linked lists.
- Initialize a pointer current to head.
- For i = 0 to k-1:
- Define size as the quotient of the count of the linked list divided by k.
- If the remainder is greater than 0, subtract 1 from the remaining variable.
- Add size nodes from current to result[i].
- Update the current pointer such that it points to the next node of the last node added to the result[i].
- Decrease remaining by 1 if it is greater than 0.
- Repeat Step 8-10 until all linked lists have been divided.
- 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
current = head
# 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
current = 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: vectorsplitListToParts(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; } }