Dadas dos listas vinculadas, inserte Nodes de la segunda lista en la primera lista en posiciones alternativas de la primera lista.
Por ejemplo, si la primera lista es 5->7->17->13->11 y la segunda es 12->10->2->4->6, la primera lista debería convertirse en 5->12->7- >10->17->2->13->4->11->6 y la segunda lista debería quedar vacía. Los Nodes de la segunda lista solo deben insertarse cuando haya posiciones disponibles. Por ejemplo, si la primera lista es 1->2->3 y la segunda lista es 4->5->6->7->8, entonces la primera lista debería convertirse en 1->4->2->5 ->3->6 y la segunda lista a 7->8.
No se permite el uso de espacio adicional (no se permite crear Nodes adicionales), es decir, la inserción debe realizarse en el lugar.
La idea es ejecutar un bucle mientras haya posiciones disponibles en el primer bucle e insertar Nodes de la segunda lista cambiando los punteros. Las siguientes son implementaciones de este enfoque.
Python3
# Python program to merge a linked list
# into another at alternate positions
class Node(object):
def __init__(self, data:int):
self.data = data
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
def push(self, new_data:int):
new_node = Node(new_data)
new_node.next = self.head
# 4. Move the head to point to
# new Node
self.head = new_node
# Function to print linked list from
# the Head
def printList(self):
temp = self.head
while temp != None:
print(temp.data)
temp = temp.next
# Main function that inserts nodes of linked
# list q into p at alternate positions.
# Since head of first list never changes
# but head of second list/ may change,
# we need single pointer for first list and
# double pointer for second list.
def merge(self, p, q):
p_curr = p.head
q_curr = q.head
# swap their positions until one
# finishes off
while p_curr != None and q_curr != None:
# Save next pointers
p_next = p_curr.next
q_next = q_curr.next
# make q_curr as next of p_curr
# change next pointer of q_curr
q_curr.next = p_next
# change next pointer of p_curr
p_curr.next = q_curr
# update current pointers for next
# iteration
p_curr = p_next
q_curr = q_next
q.head = q_curr
# Driver code
llist1 = LinkedList()
llist2 = LinkedList()
# Creating Linked lists
# 1.
llist1.push(3)
llist1.push(2)
llist1.push(1)
llist1.push(0)
# 2.
for i in range(8, 3, -1):
llist2.push(i)
print("First Linked List:")
llist1.printList()
print("Second Linked List:")
llist2.printList()
# Merging the LLs
llist1.merge(p=llist1, q=llist2)
print("Modified first linked list:")
llist1.printList()
print("Modified second linked list:")
llist2.printList()
# This code is contributed by Deepanshu Mehta
Producción:
First Linked List: 1 2 3 Second Linked List: 4 5 6 7 8 Modified First Linked List: 1 4 2 5 3 6 Modified Second Linked List: 7 8
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Fusionar una lista vinculada en otra lista vinculada en posiciones alternativas para obtener 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