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 (simple):
el enfoque más simple itera sobre la lista de fuentes y extrae Nodes de la fuente y alternativamente los coloca al frente (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.
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
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.
Consulte el artículo completo sobre la división alterna de una lista enlazada individual determinada | ¡ Establezca 1 para más detalles!
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