Splitting starting N nodes into new Circular Linked List while preserving the old nodes | C ++ implementation of the approach ; Function to add a node to the empty list ; If not empty ; Creating a node dynamically ; Assigning the data ; Creating the link ; Function to add a node to the beginning of the list ; If list is empty ; Create node ; Assign data ; Function to traverse and print the list ; If list is empty ; Pointing to the first Node of the list ; Traversing the list ; Function to find the length of the CircularLinkedList ; Stores the length ; List is empty ; Iterator Node to traverse the List ; Return the length of the list ; Function to split the first k nodes into a new CircularLinkedList and the remaining nodes stay in the original CircularLinkedList ; Empty Node for reference ; Check if the list is empty If yes , then return NULL ; NewLast will contain the last node of the new split list itr to iterate the node till the required node ; Update NewLast to the required node and link the last to the start of rest of the list ; Return the last node of the required list ; Driver code ; Create a new list for the starting k nodes ; Append the new last node into the new list ; Print the new lists
#include <bits/stdc++.h> NEW_LINE using namespace std ; class CircularLinkedList { public : struct Node { int data ; Node * next ; } ; Node * last ; Node * addToEmpty ( int data ) { if ( last != NULL ) return last ; Node * temp = new Node ( ) ; temp -> data = data ; last = temp ; last -> next = last ; return last ; } Node * addBegin ( int data ) { if ( last == NULL ) return addToEmpty ( data ) ; Node * temp = new Node ( ) ; temp -> data = data ; temp -> next = last -> next ; last -> next = temp ; return last ; } void traverse ( ) { Node * p ; if ( last == NULL ) { cout << ( " List ▁ is ▁ empty . " ) ; return ; } p = last -> next ; do { cout << p -> data << " ▁ " ; p = p -> next ; } while ( p != last -> next ) ; cout << endl ; } int length ( ) { int x = 0 ; if ( last == NULL ) return x ; Node * itr = last -> next ; while ( itr -> next != last -> next ) { x ++ ; itr = itr -> next ; } return ( x + 1 ) ; } Node * split ( int k ) { Node * pass = new Node ( ) ; if ( last == NULL ) return last ; Node * newLast , * itr = last ; for ( int i = 0 ; i < k ; i ++ ) { itr = itr -> next ; } newLast = itr ; pass -> next = itr -> next ; newLast -> next = last -> next ; last -> next = pass -> next ; return newLast ; } } ; int main ( ) { CircularLinkedList * clist = new CircularLinkedList ( ) ; clist -> last = NULL ; clist -> addToEmpty ( 12 ) ; clist -> addBegin ( 10 ) ; clist -> addBegin ( 8 ) ; clist -> addBegin ( 6 ) ; clist -> addBegin ( 4 ) ; clist -> addBegin ( 2 ) ; cout << ( " Original ▁ list : " ) ; clist -> traverse ( ) ; int k = 4 ; CircularLinkedList * clist2 = new CircularLinkedList ( ) ; clist2 -> last = clist -> split ( k ) ; cout << ( " The ▁ new ▁ lists ▁ are : " ) ; clist2 -> traverse ( ) ; clist -> traverse ( ) ; }