Escriba una función AlternatingSplit() que tome una lista y divida sus Nodes para hacer dos listas más pequeñas ‘a’ y ‘b’. Las sublistas deben estar hechas de elementos alternos en la lista original. Entonces, si la lista original es 0->1->0->1->0->1, entonces una sublista debería ser 0->0->0 y la otra debería ser 1->1->1.
Método 1 (Simple)
El enfoque más simple itera sobre la lista de fuentes y extrae Nodes de la fuente y alternativamente los coloca al principio (o al principio) de ‘a’ y b’. La única parte extraña es que los Nodes estarán en el orden inverso al que ocurrió en la lista de origen. El método 2 inserta el Node al final haciendo un seguimiento del último Node en las sublistas.
C++
/* C++ Program to alternatively split
a linked list into two halves */
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node
{
public:
int data;
Node* next;
};
/* pull off the front node of
the source and put it in dest */
void MoveNode(Node** destRef, Node** sourceRef) ;
/* Given the source list, split its
nodes into two shorter lists. If we number
the elements 0, 1, 2, ... then all the even
elements should go in the first list, and
all the odd elements in the second. The
elements in the new lists may be in any order. */
void AlternatingSplit(Node* source, Node** aRef,
Node** bRef)
{
/* split the nodes of source
to these 'a' and 'b' lists */
Node* a = NULL;
Node* b = NULL;
Node* current = source;
while (current != NULL)
{
MoveNode(&a, ¤t); /* Move a node to list 'a' */
if (current != NULL)
{
MoveNode(&b, ¤t); /* Move a node to list 'b' */
}
}
*aRef = a;
*bRef = b;
}
/* Take the node from the front of
the source, and move it to the front
of the dest. It is an error to call
this with the source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
After calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3}
*/
void MoveNode(Node** destRef, Node** sourceRef)
{
/* the front source node */
Node* newNode = *sourceRef;
assert(newNode != NULL);
/* Advance the source pointer */
*sourceRef = newNode->next;
/* Link the old dest off the new node */
newNode->next = *destRef;
/* Move dest to point to the new node */
*destRef = newNode;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at
the beginning of the linked list */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes
in a given linked list */
void printList(Node *node)
{
while(node!=NULL)
{
cout<<node->data<<" ";
node = node->next;
}
}
/* Driver code*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
Node* a = NULL;
Node* b = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 0->1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
push(&head, 0);
cout<<"Original linked List: ";
printList(head);
/* Remove duplicates from linked list */
AlternatingSplit(head, &a, &b);
cout<<"\nResultant Linked List 'a' : ";
printList(a);
cout<<"\nResultant Linked List 'b' : ";
printList(b);
return 0;
}
// This code is contributed by rathbhupendra
C
/*Program to alternatively split a linked list into two halves */
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* pull off the front node of the source and put it in dest */
void MoveNode(struct Node** destRef, struct Node** sourceRef) ;
/* Given the source list, split its nodes into two shorter lists.
If we number the elements 0, 1, 2, ... then all the even elements
should go in the first list, and all the odd elements in the second.
The elements in the new lists may be in any order. */
void AlternatingSplit(struct Node* source, struct Node** aRef,
struct Node** bRef)
{
/* split the nodes of source to these 'a' and 'b' lists */
struct Node* a = NULL;
struct Node* b = NULL;
struct Node* current = source;
while (current != NULL)
{
MoveNode(&a, ¤t); /* Move a node to list 'a' */
if (current != NULL)
{
MoveNode(&b, ¤t); /* Move a node to list 'b' */
}
}
*aRef = a;
*bRef = b;
}
/* Take the node from the front of the source, and move it to the front of the dest.
It is an error to call this with the source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
After calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3}
*/
void MoveNode(struct Node** destRef, struct Node** sourceRef)
{
/* the front source node */
struct Node* newNode = *sourceRef;
assert(newNode != NULL);
/* Advance the source pointer */
*sourceRef = newNode->next;
/* Link the old dest off the new node */
newNode->next = *destRef;
/* Move dest to point to the new node */
*destRef = newNode;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node* a = NULL;
struct Node* b = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 0->1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
push(&head, 0);
printf("\n Original linked List: ");
printList(head);
/* Remove duplicates from linked list */
AlternatingSplit(head, &a, &b);
printf("\n Resultant Linked List 'a' ");
printList(a);
printf("\n Resultant Linked List 'b' ");
printList(b);
getchar();
return 0;
}
Python
# Python program to alternatively split
# a linked list into two halves
# Node class
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# Given the source list, split its
# nodes into two shorter lists. If we number
# the elements 0, 1, 2, ... then all the even
# elements should go in the first list, and
# all the odd elements in the second. The
# elements in the new lists may be in any order.
def AlternatingSplit(self, a, b):
first = self.head
second = first.next
while (first is not None and
second is not None and
first.next is not None):
# Move a node to list 'a'
self.MoveNode(a, first)
# Move a node to list 'b'
self.MoveNode(b, second)
first = first.next.next
if first is None:
break
second = first.next
# Pull off the front node of the
# source and put it in dest
def MoveNode(self, dest, node):
# Make the new node
new_node = Node(node.data)
if dest.head is None:
dest.head = new_node
else:
# Link the old dest off the new node
new_node.next = dest.head
# Move dest to point to the new node
dest.head = new_node
# UTILITY FUNCTIONS
# Function to insert a node at
# the beginning of the linked list
def push(self, data):
# 1 & 2 allocate the Node &
# put the data
new_node = Node(data)
# Make the next of new Node as head
new_node.next = self.head
# Move the head to point to new Node
self.head = new_node
# Function to print nodes
# in a given linked list
def printList(self):
temp = self.head
while temp:
print temp.data,
temp = temp.next
print("")
# Driver Code
if __name__ == "__main__":
# Start with empty list
llist = LinkedList()
a = LinkedList()
b = LinkedList()
# Created linked list will be
# 0->1->2->3->4->5
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
llist.push(0)
llist.AlternatingSplit(a, b)
print "Original Linked List: ",
llist.printList()
print "Resultant Linked List 'a' : ",
a.printList()
print "Resultant Linked List 'b' : ",
b.printList()
# This code is contributed by kevalshah5
Javascript
<script>
// JavaScript program to alternatively split
// a linked list into two halves
// Node class
class Node{
constructor(data,next = null){
this.data = data
this.next = next
}
}
class LinkedList
{
constructor()
{
this.head = null
}
// Given the source list, split its
// nodes into two shorter lists. If we number
// the elements 0, 1, 2, ... then all the even
// elements should go in the first list, and
// all the odd elements in the second. The
// elements in the new lists may be in any order.
AlternatingSplit(a, b){
let first = this.head
let second = first.next
while (first != null &&
second != null &&
first.next != null){
// Move a node to list 'a'
this.MoveNode(a, first)
// Move a node to list 'b'
this.MoveNode(b, second)
first = first.next.next
if(first == null)
break
second = first.next
}
}
// Pull off the front node of the
// source and put it in dest
MoveNode(dest, node){
// Make the new node
let new_node = new Node(node.data)
if(dest.head == null)
dest.head = new_node
else{
// Link the old dest off the new node
new_node.next = dest.head
// Move dest to point to the new node
dest.head = new_node
}
}
// UTILITY FUNCTIONS
// Function to insert a node at
// the beginning of the linked list
push(data){
// 1 & 2 allocate the Node &
// put the data
let new_node = new Node(data)
// Make the next of new Node as head
new_node.next = this.head
// Move the head to point to new Node
this.head = new_node
}
// Function to print nodes
// in a given linked list
printList(){
let temp = this.head
while(temp){
document.write(temp.data," ");
temp = temp.next
}
document.write("</br>")
}
}
// Driver Code
// Start with empty list
let llist = new LinkedList()
let a = new LinkedList()
let b = new LinkedList()
// Created linked list will be
// 0->1->2->3->4->5
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
llist.push(0)
llist.AlternatingSplit(a, b)
document.write("Original Linked List: ");
llist.printList()
document.write("Resultant Linked List 'a' : ");
a.printList()
document.write("Resultant Linked List 'b' : ");
b.printList()
// This code is contributed by shinjanpatra
</script>
Producción:
Original linked List: 0 1 2 3 4 5 Resultant Linked List 'a' : 4 2 0 Resultant Linked List 'b' : 5 3 1
Complejidad de tiempo: O(n)
donde n es un número de Nodes en la lista enlazada dada.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Método 2 (usando Nodes ficticios)
Este es un enfoque alternativo que crea las sublistas en el mismo orden que la lista de origen. El código utiliza Nodes de encabezado ficticios temporales para las listas ‘a’ y ‘b’ a medida que se crean. Cada sublista tiene un puntero de «cola» que apunta a su último Node actual, de esa manera se pueden agregar fácilmente nuevos Nodes al final de cada lista. Los Nodes ficticios dan a los punteros de cola algo a lo que apuntar inicialmente. Los Nodes ficticios son eficientes en este caso porque son temporales y están asignados en la pila. Alternativamente, los «punteros de referencia» locales (que siempre apuntan al último puntero de la lista en lugar del último Node) podrían usarse para evitar los Nodes ficticios.
C++
void AlternatingSplit(Node* source,
Node** aRef, Node** bRef)
{
Node aDummy;
/* points to the last node in 'a' */
Node* aTail = &aDummy;
Node bDummy;
/* points to the last node in 'b' */
Node* bTail = &bDummy;
Node* current = source;
aDummy.next = NULL;
bDummy.next = NULL;
while (current != NULL)
{
MoveNode(&(aTail->next), ¤t); /* add at 'a' tail */
aTail = aTail->next; /* advance the 'a' tail */
if (current != NULL)
{
MoveNode(&(bTail->next), ¤t);
bTail = bTail->next;
}
}
*aRef = aDummy.next;
*bRef = bDummy.next;
}
// This code is contributed
// by rathbhupendra
C
void AlternatingSplit(struct Node* source, struct Node** aRef,
struct Node** bRef)
{
struct Node aDummy;
struct Node* aTail = &aDummy; /* points to the last node in 'a' */
struct Node bDummy;
struct Node* bTail = &bDummy; /* points to the last node in 'b' */
struct Node* current = source;
aDummy.next = NULL;
bDummy.next = NULL;
while (current != NULL)
{
MoveNode(&(aTail->next), ¤t); /* add at 'a' tail */
aTail = aTail->next; /* advance the 'a' tail */
if (current != NULL)
{
MoveNode(&(bTail->next), ¤t);
bTail = bTail->next;
}
}
*aRef = aDummy.next;
*bRef = bDummy.next;
}
Java
static void AlternatingSplit(Node source, Node aRef,
Node bRef)
{
Node aDummy = new Node();
Node aTail = aDummy; /* points to the last node in 'a' */
Node bDummy = new Node();
Node bTail = bDummy; /* points to the last node in 'b' */
Node current = source;
aDummy.next = null;
bDummy.next = null;
while (current != null)
{
MoveNode((aTail.next), current); /* add at 'a' tail */
aTail = aTail.next; /* advance the 'a' tail */
if (current != null)
{
MoveNode((bTail.next), current);
bTail = bTail.next;
}
}
aRef = aDummy.next;
bRef = bDummy.next;
}
// This code is contributed by rutvik_56
Python3
def AlternatingSplit(source, aRef, bRef): aDummy = Node(); aTail = aDummy; ''' points to the last Node in 'a' ''' bDummy = Node(); bTail = bDummy; ''' points to the last Node in 'b' ''' current = source; aDummy.next = None; bDummy.next = None; while (current != None): MoveNode((aTail.next), current); ''' add at 'a' tail ''' aTail = aTail.next; ''' advance the 'a' tail ''' if (current != None): MoveNode((bTail.next), current); bTail = bTail.next; aRef = aDummy.next; bRef = bDummy.next; # This code is contributed by umadevi9616
C#
static void AlternatingSplit(Node source, Node aRef,
Node bRef)
{
Node aDummy = new Node();
Node aTail = aDummy; /* points to the last node in 'a' */
Node bDummy = new Node();
Node bTail = bDummy; /* points to the last node in 'b' */
Node current = source;
aDummy.next = null;
bDummy.next = null;
while (current != null)
{
MoveNode((aTail.next), current); /* add at 'a' tail */
aTail = aTail.next; /* advance the 'a' tail */
if (current != null)
{
MoveNode((bTail.next), current);
bTail = bTail.next;
}
}
aRef = aDummy.next;
bRef = bDummy.next;
}
// This code is contributed by pratham_76
Javascript
<script>
function AlternatingSplit( source, aRef,
bRef)
{
var aDummy = new Node();
var aTail = aDummy; /* points to the last node in 'a' */
var bDummy = new Node();
var bTail = bDummy; /* points to the last node in 'b' */
var current = source;
aDummy.next = null;
bDummy.next = null;
while (current != null)
{
MoveNode((aTail.next), current); /* add at 'a' tail */
aTail = aTail.next; /* advance the 'a' tail */
if (current != null)
{
MoveNode((bTail.next), current);
bTail = bTail.next;
}
}
aRef = aDummy.next;
bRef = bDummy.next;
}
// This code contributed by aashish1995
</script>
Complejidad de tiempo: O(n)
donde n es el número de Nodes en la lista enlazada dada.
Espacio Auxiliar: O(1)
Como se utiliza el espacio adicional constante.
Fuente: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto, o encuentre mejores formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA