Dada una lista unida L 0 -> L 1 -> … -> L n-1 -> L n . Reorganice los Nodes en la lista para que la nueva lista formada sea: L 0 -> L n -> L 1 -> L n-1 -> L 2 -> L n-2 …
Debe hacer esto en su lugar sin alterando los valores de los Nodes.
Ejemplos:
Input: 1 -> 2 -> 3 -> 4 Output: 1 -> 4 -> 2 -> 3 Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 5 -> 2 -> 4 -> 3
Solución simple:
1) Initialize current node as head.
2) While next of current node is not null, do following
a) Find the last node, remove it from the end and insert it as next
of the current node.
b) Move current to next to next of current
La complejidad temporal de la solución simple anterior es O(n 2 ) donde n es el número de Nodes en la lista enlazada.
Mejor solución:
1) Copie el contenido de la lista vinculada dada a un vector.
2) Reorganizar el vector dado intercambiando Nodes de ambos extremos.
3) Copie el vector modificado nuevamente a la lista enlazada.
Implementación de este enfoque: https://ide.geeksforgeeks.org/1eGSEy
Gracias a Arushi Dhamija por sugerir este enfoque.
Solución eficiente:
1) Find the middle point using tortoise and hare method. 2) Split the linked list into two halves using found middle point in step 1. 3) Reverse the second half. 4) Do alternate merge of first and second halves.
La complejidad temporal de esta solución es O(n).
A continuación se muestra la implementación de este método.
Python3
# Python program to rearrange linked list # in place # Node Class class Node: # Constructor to create # a new node def __init__(self, d): self.data = d self.next = None def printlist(node): if(node == None): return while(node != None): print(node.data," -> ", end = "") node = node.next def reverselist(node): prev = None curr = node next=None while (curr != None): next = curr.next curr.next = prev prev = curr curr = next node = prev return node def rearrange(node): # 1) Find the middle point using # tortoise and hare method slow = node fast = slow.next while (fast != None and fast.next != None): slow = slow.next fast = fast.next.next # 2) Split the linked list in # two halves # node1, head of first half # 1 -> 2 -> 3 # node2, head of second half # 4 -> 5 node1 = node node2 = slow.next slow.next = None # 3) Reverse the second half, # i.e., 5 -> 4 node2 = reverselist(node2) # 4) Merge alternate nodes # Assign dummy Node node = Node(0) # curr is the pointer to this # dummy Node, which will be # used to form the new list curr = node while (node1 != None or node2 != None): # First add the element from # first list if (node1 != None): curr.next = node1 curr = curr.next node1 = node1.next # Then add the element from # second list if(node2 != None): curr.next = node2 curr = curr.next node2 = node2.next # Assign the head of the new list # to head pointer node = node.next head = None head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) # Print original list printlist(head) # Rearrange list as per ques rearrange(head) print() # Print modified list printlist(head) # This code is contributed by ab2127
Producción:
1 -> 2 -> 3 -> 4 -> 5 1 -> 5 -> 2 -> 4 -> 3
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Gracias a Gaurav Ahirwar por sugerir el enfoque anterior.
Otro enfoque:
1. Tome dos punteros prev y curr, que contienen las direcciones de head y head-> next.
2. Compare sus datos e intercambie.
Después de eso, se forma una nueva lista enlazada.
A continuación se muestra la implementación:
Python3
# Python3 code to rearrange linked list # in place class Node: def __init__(self, x): self.data = x self.next = None # Function for rearranging a # linked list with high and # low value def rearrange(head): # Base case if (head == None): return head # Two pointer variable prev, curr = head, head.next while (curr): # Swap function for swapping # data if (prev.data > curr.data): prev.data, curr.data = curr.data, prev.data # Swap function for swapping data if (curr.next and curr.next.data > curr.data): curr.next.data, curr.data = curr.data, curr.next.data prev = curr.next if (not curr.next): break curr = curr.next.next return head # Function to insert a node in the # linked list at the beginning def push(head, k): tem = Node(k) 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 # Driver code if __name__ == '__main__': head = None # Let create a linked list # 9 . 6 . 8 . 3 . 7 head = push(head, 7) head = push(head, 3) head = push(head, 8) head = push(head, 6) head = push(head, 9) head = rearrange(head) display(head) # This code is contributed by mohit kumar 29
Producción:
6 9 3 8 7
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Gracias a Aditya por sugerir este enfoque.
Otro enfoque: (usando la recursividad)
- Mantenga un puntero en el Node principal y vaya hasta el último Node usando recursividad
- Una vez que se alcanza el último Node, comience a intercambiar el último Node con el siguiente Node principal
- Mover el puntero de la cabeza al siguiente Node
- Repita esto hasta que la cabeza y el último Node se encuentren o queden adyacentes entre sí.
- Una vez que se cumplió la condición de parada, debemos descartar los Nodes de la izquierda para corregir el bucle creado en la lista al intercambiar Nodes.
Python3
# Python3 program to implement
# the above approach
class Node:
def __init__(self, key):
self.data = key
self.next = None
left = None
# Function to print the list
def printlist(head):
while (head != None):
print(head.data, end = " ")
if (head.next != None):
print("->", end = "")
head = head.next
print()
# Function to rearrange
def rearrange(head):
global left
if (head != None):
left = head
reorderListUtil(left)
def reorderListUtil(right):
global left
if (right == None):
return
reorderListUtil(right.next)
# We set left = null, when we
# reach stop condition, so no
# processing required after that
if (left == None):
return
# Stop condition: odd case :
# left = right, even
# case : left.next = right
if (left != right and
left.next != right):
temp = left.next
left.next = right
right.next = temp
left = temp
else:
# Stop condition , set null
# to left nodes
if (left.next == right):
# Even case
left.next.next = None
left = None
else:
# Odd case
left.next = None
left = None
# Driver code
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# Print original list
printlist(head)
# Modify the list
rearrange(head)
# Print modified list
printlist(head)
# This code is contributed by patel2127
Producción:
1 ->2 ->3 ->4 ->5 1 ->5 ->2 ->4 ->3
Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(n), para pila recursiva donde n representa la longitud de la lista enlazada dada.
Consulte el artículo completo sobre Reorganizar una lista vinculada dada en el lugar. ¡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