Given a circular linked list with N nodes and an integer K where 0 < K < N, the task is to split the first K nodes into a new list and at the same time preserving the rest of the nodes in the original circular linked list.
Examples:
Input: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8, K = 3
Output:
Original list:
2 3 4 5 6 7 8
The new lists are:
2 3 4
5 6 7 8Input: 2 -> 4 -> 6 -> 8- > 10 -> 12, N = 4
Output:
Original list:
2 4 6 8 10 12
The new lists are:
2 4 6 8
10 12
Approach:
- Traverse an iterator until the required node i.e. the Kth node.
- Point the node just previous to the Kth node to the head of the original list.
- Point the last node of the original list to the Kth node.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;class CircularLinkedList{ public: struct Node { int data; Node* next; }; Node* last; // Function to add a node to the empty list Node* addToEmpty(int data) { // If not empty if (last != NULL) return last; // Creating a node dynamically Node *temp = new Node(); // Assigning the data temp->data = data; last = temp; // Creating the link last->next = last; return last; } // Function to add a node to the // beginning of the list Node* addBegin(int data) { // If list is empty if (last == NULL) return addToEmpty(data); // Create node Node *temp = new Node(); // Assign data temp->data = data; temp->next = last->next; last->next = temp; return last; } // Function to traverse and print the list void traverse() { Node* p; // If list is empty if (last == NULL) { cout<<("List is empty."); return; } // Pointing to the first Node of the list p = last->next; // Traversing the list do { cout << p->data << " "; p = p->next; } while (p != last->next); cout << endl; } // Function to find the length of the CircularLinkedList int length() { // Stores the length int x = 0; // List is empty if (last == NULL) return x; // Iterator Node to traverse the List Node* itr = last->next; while (itr->next != last->next) { x++; itr = itr->next; } // Return the length of the list return (x + 1); } // Function to split the first k nodes into // a new CircularLinkedList and the remaining // nodes stay in the original CircularLinkedList Node* split(int k) { // Empty Node for reference Node* pass = new Node(); // Check if the list is empty // If yes, then return NULL if (last == NULL) return last; // NewLast will contain the last node of // the new split list // itr to iterate the node till // the required node Node* newLast, *itr = last; for (int i = 0; i < k; i++) { itr = itr->next; } // Update NewLast to the required node and // link the last to the start of rest of the list newLast = itr; pass->next = itr->next; newLast->next = last->next; last->next = pass->next; // Return the last node of the required list return newLast; }}; // Driver codeint 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; // Create a new list for the starting k nodes CircularLinkedList* clist2 = new CircularLinkedList(); // Append the new last node into the new list clist2->last = clist->split(k); // Print the new lists cout<<("The new lists are:"); clist2->traverse(); clist->traverse();}// This code is contributed by Arnab Kundu |
Java
// Java implementation of the approachpublic class CircularLinkedList { Node last; static class Node { int data; Node next; }; // Function to add a node to the empty list public Node addToEmpty(int data) { // If not empty if (this.last != null) return this.last; // Creating a node dynamically Node temp = new Node(); // Assigning the data temp.data = data; this.last = temp; // Creating the link this.last.next = this.last; return last; } // Function to add a node to the // beginning of the list public Node addBegin(int data) { // If list is empty if (last == null) return addToEmpty(data); // Create node Node temp = new Node(); // Assign data temp.data = data; temp.next = this.last.next; this.last.next = temp; return this.last; } // Function to traverse and print the list public void traverse() { Node p; // If list is empty if (this.last == null) { System.out.println("List is empty."); return; } // Pointing to the first Node of the list p = this.last.next; // Traversing the list do { System.out.print(p.data + " "); p = p.next; } while (p != this.last.next); System.out.println(""); } // Function to find the length of the CircularLinkedList public int length() { // Stores the length int x = 0; // List is empty if (this.last == null) return x; // Iterator Node to traverse the List Node itr = this.last.next; while (itr.next != this.last.next) { x++; itr = itr.next; } // Return the length of the list return (x + 1); } // Function to split the first k nodes into // a new CircularLinkedList and the remaining // nodes stay in the original CircularLinkedList public Node split(int k) { // Empty Node for reference Node pass = new Node(); // Check if the list is empty // If yes, then return null if (this.last == null) return this.last; // NewLast will contain the last node of // the new split list // itr to iterate the node till // the required node Node newLast, itr = this.last; for (int i = 0; i < k; i++) { itr = itr.next; } // Update NewLast to the required node and // link the last to the start of rest of the list newLast = itr; pass.next = itr.next; newLast.next = this.last.next; this.last.next = pass.next; // Return the last node of the required list return newLast; } // Driver code public static void main(String[] args) { 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); System.out.println("Original list:"); clist.traverse(); int k = 4; // Create a new list for the starting k nodes CircularLinkedList clist2 = new CircularLinkedList(); // Append the new last node into the new list clist2.last = clist.split(k); // Print the new lists System.out.println("The new lists are:"); clist2.traverse(); clist.traverse(); }} |
Python3
# Python3 implementation of the approach # Node of Linked Listclass Node: def __init__(self, x): self.data = x self.next = None # Function to add a node to the empty listdef addToEmpty(last, data): # If not empty if (last != None): return last # Assigning the data temp = Node(data) last = temp # Creating the link last.next = last return last# Function to add a node to the# beginning of the listdef addBegin(last, data): # If list is empty if (last == None): return addToEmpty(data) # Create node temp = Node(data) temp.next = last.next last.next = temp return last# Function to traverse and print listdef traverse(last): # If list is empty if (last == None): print("List is empty.") return # Pointing to the first Node of the list p = last.next # Traversing the list while True: print(p.data, end = " ") p = p.next if p == last.next: break print()# Function to find the length of # the CircularLinkedListdef length(last): # Stores the length x = 0 # List is empty if (last == None): return x # Iterator Node to traverse the List itr = last.next while (itr.next != last.next): x += 1 itr = itr.next # Return the length of the list return (x + 1)# Function to split the first k nodes into# a new CircularLinkedList and the remaining# nodes stay in the original CircularLinkedListdef split(last, k): # Empty Node for reference passs = Node(-1) # Check if the list is empty # If yes, then return NULL if (last == None): return last # NewLast will contain the last node of # the new split list itr to iterate the # node till the required node itr = last for i in range(k): itr = itr.next # Update NewLast to the required node # and link the last to the start of # rest of the list newLast = itr passs.next = itr.next newLast.next = last.next last.next = passs.next # Return the last node of the # required list return newLast# Driver codeif __name__ == '__main__': clist = None clist = addToEmpty(clist, 12) clist = addBegin(clist, 10) clist = addBegin(clist, 8) clist = addBegin(clist, 6) clist = addBegin(clist, 4) clist = addBegin(clist, 2) print("Original list:", end = "") traverse(clist) k = 4 # Append the new last node # into the new list clist2 = split(clist, k) # Print the new lists print("The new lists are:", end = "") traverse(clist2) traverse(clist)# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System; public class CircularLinkedList{ public Node last; public class Node { public int data; public Node next; }; // Function to add a node to the empty list public Node addToEmpty(int data) { // If not empty if (this.last != null) return this.last; // Creating a node dynamically Node temp = new Node(); // Assigning the data temp.data = data; this.last = temp; // Creating the link this.last.next = this.last; return last; } // Function to add a node to the // beginning of the list public Node addBegin(int data) { // If list is empty if (last == null) return addToEmpty(data); // Create node Node temp = new Node(); // Assign data temp.data = data; temp.next = this.last.next; this.last.next = temp; return this.last; } // Function to traverse and print the list public void traverse() { Node p; // If list is empty if (this.last == null) { Console.WriteLine("List is empty."); return; } // Pointing to the first Node of the list p = this.last.next; // Traversing the list do { Console.Write(p.data + " "); p = p.next; } while (p != this.last.next); Console.WriteLine(""); } // Function to find the length of the CircularLinkedList public int length() { // Stores the length int x = 0; // List is empty if (this.last == null) return x; // Iterator Node to traverse the List Node itr = this.last.next; while (itr.next != this.last.next) { x++; itr = itr.next; } // Return the length of the list return (x + 1); } // Function to split the first k nodes into // a new CircularLinkedList and the remaining // nodes stay in the original CircularLinkedList public Node split(int k) { // Empty Node for reference Node pass = new Node(); // Check if the list is empty // If yes, then return null if (this.last == null) return this.last; // NewLast will contain the last node of // the new split list // itr to iterate the node till // the required node Node newLast, itr = this.last; for (int i = 0; i < k; i++) { itr = itr.next; } // Update NewLast to the required node and // link the last to the start of rest of the list newLast = itr; pass.next = itr.next; newLast.next = this.last.next; this.last.next = pass.next; // Return the last node of the required list return newLast; } // Driver code public static void Main(String[] args) { 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); Console.WriteLine("Original list:"); clist.traverse(); int k = 4; // Create a new list for the starting k nodes CircularLinkedList clist2 = new CircularLinkedList(); // Append the new last node into the new list clist2.last = clist.split(k); // Print the new lists Console.WriteLine("The new lists are:"); clist2.traverse(); clist.traverse(); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approachclass Node{ constructor() { let data; let next; }}// Function to add a node to the empty listfunction addToEmpty(last,data){ // If not empty if (last != null) return last; // Creating a node dynamically let temp = new Node(); // Assigning the data temp.data = data; last = temp; // Creating the link last.next = last; return last;}// Function to add a node to the // beginning of the listfunction addBegin(last, data){ // If list is empty if (last == null) return addToEmpty(data); // Create node let temp = new Node(); // Assign data temp.data = data; temp.next = last.next; last.next = temp; return last;}// Function to traverse and print the listfunction traverse(last){ let p; // If list is empty if (last == null) { document.write("List is empty.<br>"); return; } // Pointing to the first Node of the list p = last.next; // Traversing the list do { document.write(p.data + " "); p = p.next; } while (p != last.next); document.write("<br>");}// Function to find the length of the CircularLinkedListfunction length(last){ // Stores the length let x = 0; // List is empty if (last == null) return x; // Iterator Node to traverse the List let itr = last.next; while (itr.next != last.next) { x++; itr = itr.next; } // Return the length of the list return (x + 1);}// Function to split the first k nodes into // a new CircularLinkedList and the remaining // nodes stay in the original CircularLinkedListfunction split(last,k){ // Empty Node for reference let pass = new Node(); // Check if the list is empty // If yes, then return null if (last == null) return last; // NewLast will contain the last node of // the new split list // itr to iterate the node till // the required node let newLast, itr = last; for (let i = 0; i < k; i++) { itr = itr.next; } // Update NewLast to the required node and // link the last to the start of rest of the list newLast = itr; pass.next = itr.next; newLast.next = last.next; last.next = pass.next; // Return the last node of the required list return newLast;}// Driver codelet clist = null; clist=addToEmpty(clist,12);clist=addBegin(clist,10);clist=addBegin(clist,8);clist=addBegin(clist,6);clist=addBegin(clist,4);clist=addBegin(clist,2);document.write("Original list:<br>");traverse(clist);let k = 4;// Append the new last node into the new listlet clist2 = split(clist, k)// Print the new listsdocument.write("The new lists are:<br>");traverse(clist2);traverse(clist);// This code is contributed by unknown2108</script> |
Output:
Original list: 2 4 6 8 10 12 The new lists are: 2 4 6 8 10 12
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
