Dada una lista enlazada, reorganícela de modo que la lista convertida tenga la forma a < b > c < d > e < f… donde a, b, c… son Nodes de datos consecutivos de la lista enlazada.
Ejemplos:
Input: 1->2->3->4
Output: 1->3->2->4
Explanation: 1 and 3 should come first before 2 and 4 in
zig-zag fashion, So resultant linked-list
will be 1->3->2->4.
Input: 11->15->20->5->10
Output: 11->20->5->15->10
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Un enfoque simple para hacer esto es ordenar la lista enlazada usando la ordenación por combinación y luego intercambiar alternativamente, pero eso requiere una complejidad de tiempo O(n Log n). Aquí n es un número de elementos en la lista enlazada.
Un enfoque eficiente que requiere tiempo O(n) es usar un solo escaneo similar a la ordenación de burbujas y luego mantener una bandera para representar en qué orden() estamos actualmente. Si los dos elementos actuales no están en ese orden, intercambie esos elementos, de lo contrario no. Consulte esto para obtener una explicación detallada de la orden de intercambio.
sigue” href=”http://geeksquiz.com/converting-an-array-of-integers-into-zig-zag-fashion/”>esto para obtener una explicación detallada del orden de intercambio.
Python
# Python code to rearrange linked list
# in zig zag fashion
# Node class
class Node:
# Constructor to initialize
# the node object
def __init__(self, data):
self.data = data
self.next = None
# This function distributes the Node
# in zigzag fashion
def zigZagList(head):
# If flag is true, then next node
# should be greater in the desired
# output.
flag = True
# Traverse linked list starting
# from head.
current = head
while (current.next != None):
# "<" relation expected
if (flag):
# If we have a situation like
# A > B > C where A, B and C
# are consecutive Nodes in list
# we get A > B < C by swapping B
# and C
if (current.data >
current.next.data):
t = current.data
current.data = current.next.data
current.next.data = t
# ">" relation expected
else :
# If we have a situation like
# A < B < C where A, B and C
# are consecutive Nodes in list we
# get A < C > B by swapping B and C
if (current.data <
current.next.data):
t = current.data
current.data = current.next.data
current.next.data = t
current = current.next
if(flag):
# flip flag for reverse checking
flag = False
else:
flag = True
return head
# Function to insert a Node in
# the linked list at the beginning.
def push(head, k):
tem = Node(0)
tem.data = k
tem.next = head
head = tem
return head
# Function to display Node of
# linked list.
def display(head):
curr = head
while (curr != None):
print(curr.data,
"->", end =" ")
curr = curr.next
print("None")
# Driver code
head = None
# create a list 4 -> 3 -> 7 ->
# 8 -> 6 -> 2 -> 1
# answer should be -> 3 7 4
# 8 2 6 1
head = push(head, 1)
head = push(head, 2)
head = push(head, 6)
head = push(head, 8)
head = push(head, 7)
head = push(head, 3)
head = push(head, 4)
print("Given linked list ")
display(head)
head = zigZagList(head)
print("Zig Zag Linked list ")
display(head)
# This code is contributed by Arnab Kundu
Producción:
Given linked list 4->3->7->8->6->2->1->NULL Zig Zag Linked list 3->7->4->8->2->6->1->NULL
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos usando espacio extra.
Otro enfoque:
en el código anterior, la función de empuje empuja el Node al frente de la lista vinculada, el código se puede modificar fácilmente para empujar el Node al final de la lista. Otra cosa a tener en cuenta es que el intercambio de datos entre dos Nodes se realiza intercambiando por valor, no intercambiando por enlaces para simplificar, para la técnica de intercambio por enlaces, consulte this .
Esto también se puede hacer recursivamente. La idea sigue siendo la misma, supongamos que el valor de la bandera determina la condición que necesitamos verificar para comparar el elemento actual. Entonces, si el indicador es 0 (o falso), el elemento actual debe ser más pequeño que el siguiente y si el indicador es 1 (o verdadero), entonces el elemento actual debe ser mayor que el siguiente. Si no, intercambie los valores de los Nodes.
Python3
# Python program for the above approach
# Node class
class Node:
# Constructor to initialize the
# node object
def __init__(self, data):
self.data = data
self.next = None
head = None
# Point Linked List
def printLL():
t = head
while (t != None):
print(t.data, end = " ->")
t = t.next
print()
# Swap both nodes
def swap(a,b):
if(a == None or
b == None):
return
temp = a.data
a.data = b.data
b.data = temp
# Rearrange the linked list
# in zig zag way
def zigZag(node, flag):
if(node == None or
node.next == None):
return node
if (flag == 0):
if (node.data >
node.next.data):
swap(node, node.next)
return zigZag(node.next, 1)
else:
if (node.data <
node.next.data):
swap(node, node.next)
return zigZag(node.next, 0)
# Driver Code
head = Node(11)
head.next = Node(15)
head.next.next = Node(20)
head.next.next.next = Node(5)
head.next.next.next.next = Node(10)
printLL();
# 0 means the current element
# should be smaller than the next
flag = 0
zigZag(head, flag)
print("LL in zig zag fashion : ")
printLL()
# This code is contributed by avanitrachhadiya2155
Producción:
11 ->15 ->20 ->5 ->10 -> LL in zig zag fashion : 11 ->20 ->5 ->15 ->10 ->
Análisis de Complejidad:
- Complejidad temporal: O(n).
El recorrido de la lista se realiza una sola vez y tiene ‘n’ elementos. - Espacio Auxiliar: O(n).
O(n) espacio adicional durante la pila recursiva.
Consulte el artículo completo sobre Reorganizar una lista vinculada en forma de zig-zag 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