Partition a Linked List into K continuous groups with difference in their sizes at most 1 | C ++ program for the above approach ; Link List Node ; Function to insert a node into the Linked List ; Allocate a new dynamic node ; Update new_node -> val ; Stores the head_ref ; Update ( * head_ref ) ; Function to split the linked list in K groups ; Stores the K groups ; If head is NULL ; Iterate until K is non - zero ; Stores the length of the linked list ; Stores the head node of the linked list ; Iterate over the linked list ; Update p ; Update N ; Iterate over the linked list ; Stores the length of the current group ; Stores the current node ; Stores the previous node ; If rem is greater than 0 ; Update p ; Decrement rem by 1 ; Iterate until x is non - zero ; If the last is equal to p ; Otherwise ; Join the link between last and the current element ; Update the last node ; Update p node ; Assign NULL to last -> next ; Push the current linked list in ans ; Decrement K ; While K greater than 0 ; Update the value of ans ; Increment K ; Print the result ; Print the value ; Update ans [ i ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct ListNode { int val ; struct ListNode * next ; } ; void push ( ListNode * * head_ref , int node_val ) { ListNode * new_node = new ListNode ( ) ; new_node -> val = node_val ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } void splitListInParts ( ListNode * head , int K ) { vector < ListNode * > ans ; if ( ! head ) { while ( K -- ) ans . push_back ( NULL ) ; } int N = 0 ; ListNode * p = head ; while ( p ) { p = p -> next ; N ++ ; } int len = N / K ; int rem = N % K ; p = head ; while ( K > 0 && p ) { int x = len ; ListNode * curr_head = p ; ListNode * last = p ; if ( rem > 0 ) { p = p -> next ; rem -- ; } while ( x -- ) { if ( last == p ) p = p -> next ; else { last -> next = p ; last = p ; p = p -> next ; } } last -> next = NULL ; ans . push_back ( curr_head ) ; K -- ; } while ( K > 0 ) { ans . push_back ( NULL ) ; K -- ; } cout << " { " ; for ( int i = 0 ; i < ans . size ( ) ; i ++ ) { cout << " { " ; while ( ans [ i ] ) { cout << ans [ i ] -> val << " ▁ " ; ans [ i ] = ans [ i ] -> next ; } cout << " } " ; if ( i != ans . size ( ) - 1 ) cout << " , ▁ " ; } cout << " } " ; } 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 ; }