Splitting starting N nodes into new Circular Linked List while preserving the old nodes

0 0 10 minutes read

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 8

Input: 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 K^th node.
Point the node just previous to the K^th node to the head of the original list.
Point the last node of the original list to the K^th 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 code
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;
 
    // 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 approach
public 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 List
class Node:
     
    def __init__(self, x):
         
        self.data = x
        self.next = None
         
# Function to add a node to the empty list
def 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 list
def 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 list
def 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 CircularLinkedList
def 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 CircularLinkedList
def 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 code
if __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 approach
using 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 approach
 
class Node
{
    constructor()
    {
        let data;
        let next;
    }
}
 
// Function to add a node to the empty list
function 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 list
function 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 list
function 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 CircularLinkedList
function 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 CircularLinkedList
function 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 code
let 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 list
let clist2 = split(clist, k)
 
// Print the new lists
document.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 zambiatek!