Dado el puntero al Node principal de una lista enlazada, la tarea es invertir la lista enlazada. Necesitamos invertir la lista cambiando los enlaces entre los Nodes.
Ejemplos:
Input : Head of following linked list 1->2->3->4->NULL Output : Linked list should be changed to, 4->3->2->1->NULL Input : Head of following linked list 1->2->3->4->5->NULL Output : Linked list should be changed to, 5->4->3->2->1->NULL Input : NULL Output : NULL Input : 1->NULL Output : 1->NULL
Método iterativo
Python3
# Python program to reverse a linked list # Time Complexity : O(n) # Space Complexity : O(n) as 'next' #variable is getting created in each loop. # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to reverse the linked list def reverse(self): prev = None current = self.head while(current is not None): next = current.next current.next = prev prev = current current = next self.head = prev # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print the LinkedList def printList(self): temp = self.head while(temp): print (temp.data,end=" ") temp = temp.next # Driver program to test above functions llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(85) print ("Given Linked List") llist.printList() llist.reverse() print ("\nReversed Linked List") llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Producción:
Given Linked List 85 15 4 20 Reversed Linked List 20 4 15 85
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Un método recursivo más simple y de cola
Python3
# Simple and tail recursive Python program to # reverse a linked list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None def reverseUtil(self, curr, prev): # If last node mark it head if curr.next is None: self.head = curr # Update next to prev node curr.next = prev return # Save curr.next node for recursive call next = curr.next # And update next curr.next = prev self.reverseUtil(next, curr) # This function mainly calls reverseUtil() # with previous as None def reverse(self): if self.head is None: return self.reverseUtil(self.head, None) # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print the LinkedList def printList(self): temp = self.head while(temp): print(temp.data,end=" ") temp = temp.next # Driver program llist = LinkedList() llist.push(8) llist.push(7) llist.push(6) llist.push(5) llist.push(4) llist.push(3) llist.push(2) llist.push(1) print("Given linked list") llist.printList() llist.reverse() print("\nReverse linked list") llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Producción
Given linked list 1 2 3 4 5 6 7 8 Reverse linked list 8 7 6 5 4 3 2 1
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Invertir una lista vinculada 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