Partition a Linked List into K continuous groups with difference in their sizes at most 1
Given a linked list consisting of N nodes and an integer K, the task is to split the given Linked List into K continuous groups such that the difference between the size of the adjacent groups after splitting is at most 1 and the groups are sorted in descending order of their lengths.
Note: A group with 0 elements can also be formed.
Examples:
Input: 1 ? 2 ? 3 ? 4, K = 5
Output: {{1}, {2}, {3}, {4}, {}}
Explanation: Required splits are {{1 -> NULL}, {2 -> NULL}, {3 -> NULL}, {4 -> NULL}, {NULL}}.Input: LL: 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8, K = 3
Output: {{1, 2, 3}, {4, 5, 6}, {7, 8}}
Approach: The given problem can be solved based on the observation that forming first N % K groups of size (N / K + 1) and the remaining K – (N % K) groups of size N / K satisfies the conditions. Follow the steps below to solve the problem:
- Initialize a vector of the linked list, says ans, that stores the K groups.
- Store the value of N / K and N % K in the variables, say L and R.
- Traverse the given linked list and perform the following steps:
- Store the value of L in a variable say X and the value of head in the variable say currHead and last.
- If the value of R is positive, then update the value of head to head->next.
- Iterate a loop until X is non-zero and perform the following steps:
- If the last node is the same as the head node then move the head node to the next node.
- Otherwise, join the links between the last node and the head node and update the last to head, and move the head node to the next node.
- Push the current Linked List as the currentHead in the vector ans[].
- If the value of K is greater than 0, then push the NULL Linked List in ans and decrement K by 1.
- After completing the above steps, print the elements of all the Linked List stored in the vector ans[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Link List Node struct ListNode { int val; struct ListNode* next; }; // Function to insert a node // into the Linked List void push(ListNode** head_ref, int node_val) { // Allocate a new dynamic node ListNode* new_node = new ListNode(); // Update new_node->val new_node->val = node_val; // Stores the head_ref new_node->next = (*head_ref); // Update (*head_ref) (*head_ref) = new_node; } // Function to split the linked list // in K groups void splitListInParts(ListNode* head, int K) { // Stores the K groups vector<ListNode*> ans; // If head is NULL if (!head) { // Iterate until K is non-zero while (K--) ans.push_back(NULL); } // Stores the length of the // linked list int N = 0; // Stores the head node of the // linked list ListNode* p = head; // Iterate over the linked list while (p) { // Update p p = p->next; // Update N N++; } int len = N / K; int rem = N % K; p = head; // Iterate over the linked list while (K > 0 && p) { // Stores the length // of the current group int x = len; // Stores the current node ListNode* curr_head = p; // Stores the previous node ListNode* last = p; // If rem is greater than 0 if (rem > 0) { // Update p p = p->next; // Decrement rem by 1 rem--; } // Iterate until x is non-zero while (x--) { // If the last is equal to p if (last == p) p = p->next; // Otherwise else { // Join the link between // last and the current // element last->next = p; // Update the last node last = p; // Update p node p = p->next; } } // Assign NULL to last->next last->next = NULL; // Push the current linked // list in ans ans.push_back(curr_head); // Decrement K K--; } // While K greater than 0 while (K > 0) { // Update the value of ans ans.push_back(NULL); // Increment K K--; } // Print the result cout << "{" ; for ( int i = 0; i < ans.size(); i++) { cout << "{" ; while (ans[i]) { // Print the value cout << ans[i]->val << " " ; // Update ans[i] ans[i] = ans[i]->next; } cout << "}" ; if (i != ans.size() - 1) cout << ", " ; } cout << "}" ; } // Driver Code int main() { ListNode* root = NULL; push(&root, 8); push(&root, 7); push(&root, 6); push(&root, 5); push(&root, 4); push(&root, 3); push(&root, 2); push(&root, 1); int K = 3; splitListInParts(root, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Link List Node static class ListNode { int val; ListNode next; }; // Function to insert a node // into the Linked List static ListNode push(ListNode head_ref, int node_val) { // Allocate a new dynamic node ListNode new_node = new ListNode(); // Update new_node.val new_node.val = node_val; // Stores the head_ref new_node.next = head_ref; // Update head_ref head_ref = new_node; return head_ref; } // Function to split the linked list // in K groups static void splitListInParts(ListNode head, int K) { // Stores the K groups Vector<ListNode> ans = new Vector<ListNode>(); // If head is null if (head == null ) { // Iterate until K is non-zero while (K-- > 0 ) ans.add( null ); } // Stores the length of the // linked list int N = 0 ; // Stores the head node of the // linked list ListNode p = head; // Iterate over the linked list while (p.next != null ) { // Update p p = p.next; // Update N N++; } int len = N / K; int rem = N % K; p = head; // Iterate over the linked list while (K > 0 && p.next != null ) { // Stores the length // of the current group int x = len; // Stores the current node ListNode curr_head = p; // Stores the previous node ListNode last = p; // If rem is greater than 0 if (rem > 0 ) { // Update p p = p.next; // Decrement rem by 1 rem--; } // Iterate until x is non-zero while (x-- > 0 ) { // If the last is equal to p if (last == p) p = p.next; // Otherwise else { // Join the link between // last and the current // element last.next = p; // Update the last node last = p; // Update p node p = p.next; } } // Assign null to last.next last.next = null ; // Push the current linked // list in ans ans.add(curr_head); // Decrement K K--; } // While K greater than 0 while (K > 0 ) { // Update the value of ans ans.add( null ); // Increment K K--; } // Print the result System.out.print( "{" ); for ( int i = 0 ; i < ans.size(); i++) { System.out.print( "{" ); while (ans.get(i) != null ) { // Print the value System.out.print(ans.get(i).val + " " ); // Update ans[i] ans.set(i, ans.get(i).next); } System.out.print( "}" ); if (i != ans.size() - 1 ) System.out.print( ", " ); } System.out.print( "}" ); } // Driver Code public static void main(String[] args) { ListNode root = new ListNode(); root = push(root, 8 ); root = push(root, 7 ); root = push(root, 6 ); root = push(root, 5 ); root = push(root, 4 ); root = push(root, 3 ); root = push(root, 2 ); root = push(root, 1 ); int K = 3 ; splitListInParts(root, K); } } // This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach # link list node class ListNode: def __init__( self , key): self .val = key self . next = None # function to insert a node # into the linked list def push(head_ref, node_val): # allocate a new dynamic node new_node = ListNode(node_val) # stores the head_ref new_node. next = head_ref return new_node # function to split the linked list in # K groups def splitListInParts(head, K): # stores the K groups ans = [] # if head is None if (head is None ): # iterate until k is non-zero while (K > 0 ): k - = 1 ans.append( None ) # stores the length of the linked list N = 0 # stores the head node of the # linked list p = head # iterative over the linked list while (p is not None ): # update p p = p. next # update N N + = 1 length = int (N / K) rem = int (N % K) p = head # iterate over the linked list while (K > 0 and p is not None ): # stores the length # of the current group x = length # stores the current node curr_head = p # stores the previous node last = p # if rem is greater than 0 if (rem > 0 ): # update p p = p. next # decrement rem by 1 rem - = 1 # iterative until x is not zero while (x > 0 ): x - = 1 # if the last is equal to p if (last = = p): p = p. next else : # join the link between # last and the current # element last. next = p # update the last node last = p # update p node p = p. next # assign null to last.next last. next = None # push the current linked list in ans ans.append(curr_head) # decrement k K - = 1 # while k greater than 0 while (K > 0 ): # update the value of ans ans.append( None ) # increment K K - = 1 # print the result print ( "{" , end = "") for i in range ( len (ans)): print ( "{" , end = " " ) while (ans[i] is not None ): # print the value print (ans[i].val, end = " " ) ans[i] = ans[i]. next print ( "}" , end = "") if (i ! = len (ans) - 1 ): print ( ", " , end = "") print ( "}" ) # driver code root = None root = push(root, 8 ) root = push(root, 7 ) root = push(root, 6 ) root = push(root, 5 ) root = push(root, 4 ) root = push(root, 3 ) root = push(root, 2 ) root = push(root, 1 ) K = 3 splitListInParts(root, K) # this code is contributed by Yash Agarwal(yashagarwal2852002) |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ // Link List Node class ListNode { public int val; public ListNode next; }; // Function to insert a node // into the Linked List static ListNode push(ListNode head_ref, int node_val) { // Allocate a new dynamic node ListNode new_node = new ListNode(); // Update new_node.val new_node.val = node_val; // Stores the head_ref new_node.next = head_ref; // Update head_ref head_ref = new_node; return head_ref; } // Function to split the linked list // in K groups static void splitListInParts(ListNode head, int K) { // Stores the K groups List<ListNode> ans = new List<ListNode>(); // If head is null if (head == null ) { // Iterate until K is non-zero while (K-- > 0) ans.Add( null ); } // Stores the length of the // linked list int N = 0; // Stores the head node of the // linked list ListNode p = head; // Iterate over the linked list while (p.next != null ) { // Update p p = p.next; // Update N N++; } int len = N / K; int rem = N % K; p = head; // Iterate over the linked list while (K > 0 && p.next != null ) { // Stores the length // of the current group int x = len; // Stores the current node ListNode curr_head = p; // Stores the previous node ListNode last = p; // If rem is greater than 0 if (rem > 0) { // Update p p = p.next; // Decrement rem by 1 rem--; } // Iterate until x is non-zero while (x-- > 0) { // If the last is equal to p if (last == p) p = p.next; // Otherwise else { // Join the link between // last and the current // element last.next = p; // Update the last node last = p; // Update p node p = p.next; } } // Assign null to last.next last.next = null ; // Push the current linked // list in ans ans.Add(curr_head); // Decrement K K--; } // While K greater than 0 while (K > 0) { // Update the value of ans ans.Add( null ); // Increment K K--; } // Print the result Console.Write( "{" ); for ( int i = 0; i < ans.Count; i++) { Console.Write( "{" ); while (ans[i] != null ) { // Print the value Console.Write(ans[i].val + " " ); // Update ans[i] ans[i] = ans[i].next; } Console.Write( "}" ); if (i != ans.Count - 1) Console.Write( ", " ); } Console.Write( "}" ); } // Driver Code public static void Main(String[] args) { ListNode root = new ListNode(); root = push(root, 8); root = push(root, 7); root = push(root, 6); root = push(root, 5); root = push(root, 4); root = push(root, 3); root = push(root, 2); root = push(root, 1); int K = 3; splitListInParts(root, K); } } // This code contributed by shikhasingrajput |
Javascript
<script> // javascript program for the above approach // Link List Node class ListNode { constructor() { this .val = 0; this .next = null ; } }; // Function to insert a node // into the Linked List function pushIn(head_ref, node_val) { // Allocate a new dynamic node var new_node = new ListNode(); // Update new_node.val new_node.val = node_val; // Stores the head_ref new_node.next = (head_ref); // Update (*head_ref) head_ref = new_node; return head_ref; } // Function to split the linked list // in K groups function splitListInParts(head, K) { // Stores the K groups var ans = []; // If head is null if (!head) { // Iterate until K is non-zero while (K--) ans.push( null ); } // Stores the length of the // linked list var N = 0; // Stores the head node of the // linked list var p = head; // Iterate over the linked list while (p) { // Update p p = p.next; // Update N N++; } var len = parseInt(N / K); var rem = N % K; p = head; // Iterate over the linked list while (K > 0 && p) { // Stores the length // of the current group var x = len; // Stores the current node var curr_head = p; // Stores the previous node var last = p; // If rem is greater than 0 if (rem > 0) { // Update p p = p.next; // Decrement rem by 1 rem--; } // Iterate until x is non-zero while (x--) { // If the last is equal to p if (last == p) p = p.next; // Otherwise else { // Join the link between // last and the current // element last.next = p; // Update the last node last = p; // Update p node p = p.next; } } // Assign null to last.next last.next = null ; // Push the current linked // list in ans ans.push(curr_head); // Decrement K K--; } // While K greater than 0 while (K > 0) { // Update the value of ans ans.push( null ); // Increment K K--; } // Print the result document.write( "{" ); for ( var i = 0; i < ans.length; i++) { document.write( "{" ); while (ans[i]) { // Print the value document.write( ans[i].val + " " ); // Update ans[i] ans[i] = ans[i].next; } document.write( "}" ); if (i != ans.length - 1) document.write( ", " ); } document.write( "}" ); } // Driver Code var root = null ; root = pushIn(root, 8); root = pushIn(root, 7); root = pushIn(root, 6); root = pushIn(root, 5); root = pushIn(root, 4); root = pushIn(root, 3); root = pushIn(root, 2); root = pushIn(root, 1); var K = 3; splitListInParts(root, K); // This code is contributed by rrrtnx. </script> |
{{1 2 3 }, {4 5 6 }, {7 8 }}
Time Complexity: O(N)
Auxiliary Space: O(N)