Dada una lista enlazada circular con N Nodes y un número entero K donde 0 < K < N , la tarea es dividir los primeros K Nodes en una nueva lista y al mismo tiempo conservar el resto de los Nodes en la lista enlazada circular original.
Ejemplos:
Entrada: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8, K = 3
Salida:
Lista original:
2 3 4 5 6 7 8
Las nuevas listas son:
2 3 4
5 6 7 8Entrada: 2 -> 4 -> 6 -> 8- > 10 -> 12, N = 4
Salida:
Lista original:
2 4 6 8 10 12
Las nuevas listas son:
2 4 6 8
10 12
Acercarse:
- Atraviese un iterador hasta el Node requerido, es decir, el K -ésimo Node.
- Apunte el Node inmediatamente anterior al K -ésimo Node al encabezado de la lista original.
- Apunte el último Node de la lista original al K -ésimo Node.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Original list: 2 4 6 8 10 12 The new lists are: 2 4 6 8 10 12
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por samarthray21 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA