Dada una lista enlazada, escribe una función para invertir cada k Node (donde k es una entrada a la función). Ejemplos:
Entradas: 1->2->3->4->5->6->7->8->NULL, k = 3
Salida: 3->2->1->6->5->4- >8->7->NULOEntradas: 1->2->3->4->5->6->7->8->NULL, k = 5
Salida: 5->4->3->2->1->8- >7->6->NULO
Ya se han discutido múltiples enfoques para el problema anterior en las publicaciones a continuación:
- Invertir una lista enlazada en grupos de tamaño determinado | Conjunto 1 -> Usar recursividad con espacio extra O(n/k)
- Invertir una lista enlazada en grupos de tamaño determinado | Conjunto 2 -> Usar pila con O(k) espacio extra
- Invierta una lista enlazada individual en grupos de tamaño determinado | Conjunto 3 -> Usar deque con O(k) espacio extra
Enfoque: este artículo se centra en un enfoque que utiliza el espacio auxiliar O(1) . A continuación se detallan los pasos a seguir:
- Realice un seguimiento del primer Node en un puntero para cada grupo de elementos k en la lista vinculada.
- Invierta el orden de los siguientes k elementos desde el primer Node del grupo actual usando este algoritmo.
- Después de invertir, el primer Node del grupo actual se convertirá en el último Node. Conéctelo con el Node k+1 de la lista enlazada.
- El k+1 Node se convertirá en el primer Node del siguiente grupo de k elementos. De manera similar, repita el proceso para cada grupo de k elementos hasta que se haya recorrido toda la lista enlazada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to reverse a linked // list in groups of given size #include <bits/stdc++.h> using namespace std; // Linked list Node class Node { public: int data; Node* next; Node(int d) { data = d; next = NULL; } }; void reverse(Node** node, int k) { if (k == 1) return; // Keeps track of the final list Node* result = NULL; // Append a new node at initial step Node* head = new Node(0); head->next = *(node); Node* next = (*node)->next; int count = 0; while (next) { count++; // Update the pointer and // iterate linked list by // using node & next pointer Node* tmp = next->next; next->next = *(node); *(node) = next; next = tmp; if (count == k - 1) { count = 0; if (result == NULL) result = *(node); // Last step to join the // reversed k-group with // the linked list tmp = head->next; tmp->next = next; head->next = *(node); head = tmp; // Move on to the next k-group *(node) = next; if (*(node)!= NULL) next = (*node)->next; } } // Process last elements Node* tmp = head->next; if (tmp) tmp->next = NULL; head->next = *(node); *(node) = result; return; } // Utility functions // Function to inserts a new // Node at front of the list void push(Node** head,int new_data) { Node* new_node = new Node(new_data); new_node->next = *(head); *(head) = new_node; } // Function to print linked list void printList(Node** head) { Node* temp = *(head); while (temp) { cout << temp->data << " "; temp = temp->next; } cout << endl; } /* Driver program to test above functions */ int main() { Node* head = NULL; /* Constructed Linked List is * 1->2->3->4->5->6->7->8->null */ push(&head,8); push(&head,7); push(&head,6); push(&head,5); push(&head,4); push(&head,3); push(&head,2); push(&head,1); reverse(&head, 3); printList(&head); return 0; } // This code is contributed by maddler.
Java
// Java program to reverse a linked // list in groups of given size class LinkedList { // head of list Node head; // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } Node reverse(Node node, int k) { if (k == 1) return node; // Keeps track of the final list Node result = null; // Append a new node at initial step Node head = new Node(0); head.next = node; Node next = node.next; int count = 0; while (next != null) { count++; // Update the pointer and // iterate linked list by // using node & next pointer Node tmp = next.next; next.next = node; node = next; next = tmp; if (count == k - 1) { count = 0; if (result == null) result = node; // Last step to join the // reversed k-group with // the linked list tmp = head.next; tmp.next = next; head.next = node; head = tmp; // Move on to the next k-group node = next; if (node != null) next = node.next; } } // Process last elements Node tmp = head.next; if (tmp != null) tmp.next = null; head.next = node; return result; } // Utility functions // Function to inserts a new // Node at front of the list public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print linked list void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList llist = new LinkedList(); /* Constructed Linked List is * 1->2->3->4->5->6->7->8->null */ llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); llist.head = llist.reverse(llist.head, 3); llist.printList(); } }
Python3
# Python program to reverse a linked # list in groups of given size # Node class class Node: # Function to initialize the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize # next as null def reverse(head, k): temp = jump = Node(0) temp.next = left = right = head while True: count = 0 while right and count < k: # use right to locate the range right = right.next count += 1 if count == k: # if size k satisfied, reverse the inner linked list pre, cur = right, left for _ in range(k): cur.next, cur, pre = pre, cur.next, cur # standard reversing jump.next, jump, left = pre, left, right # connect two k-groups else: return temp.next # Utility functions # Function to inserts a new # Node at front of the list def push(head, new_data): new_node = Node(new_data) new_node.next = head head = new_node return head # Function to print linked list def printList(head): temp = head while(temp): print(temp.data) temp = temp.next # Driver program to test above functions head = None # Constructed Linked List is # 1->2->3->4->5->6->7->8->null head = push(head, 8) head = push(head, 7) head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) head = reverse(head, 3) printList(head) # This code is contributed by rj13to.
C#
using System; // C# program to reverse a linked // list in groups of given size public class List { // head of list public Node head; // Linked list Node public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } Node reverse(Node node, int k) { if (k == 1) return node; // Keeps track of the readonly list Node result = null; // Append a new node at initial step Node head = new Node(0); head.next = node; Node next = node.next; int count = 0; while (next != null) { count++; // Update the pointer and // iterate linked list by // using node & next pointer Node tmp1 = next.next; next.next = node; node = next; next = tmp1; if (count == k - 1) { count = 0; if (result == null) result = node; // Last step to join the // reversed k-group with // the linked list tmp1 = head.next; tmp1.next = next; head.next = node; head = tmp1; // Move on to the next k-group node = next; if (node != null) next = node.next; } } // Process last elements Node tmp = head.next; if (tmp != null) tmp.next = null; head.next = node; return result; } // Utility functions // Function to inserts a new // Node at front of the list public void Push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print linked list void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } /* Driver program to test above functions */ public static void Main(String []args) { List llist = new List(); /* * Constructed Linked List is 1->2->3->4->5->6->7->8->null */ llist.Push(8); llist.Push(7); llist.Push(6); llist.Push(5); llist.Push(4); llist.Push(3); llist.Push(2); llist.Push(1); llist.head = llist.reverse(llist.head, 3); llist.printList(); } } // This code is contributed by gauravrajput1
Javascript
<script> // javascript program to reverse a linked // list in groups of given size // head of list var head; // Linked list Node class Node { constructor(val) { this.data = val; this.next = null; } } function reverse(node , k) { if (k == 1) return node; // Keeps track of the final list var result = null; // Append a new node at initial step var head = new Node(0); head.next = node; var next = node.next; var count = 0; while (next != null) { count++; // Update the pointer and // iterate linked list by // using node & next pointer var tmp = next.next; next.next = node; node = next; next = tmp; if (count == k - 1) { count = 0; if (result == null) result = node; // Last step to join the // reversed k-group with // the linked list tmp = head.next; tmp.next = next; head.next = node; head = tmp; // Move on to the next k-group node = next; if (node != null) next = node.next; } } // Process last elements var tmp = head.next; if (tmp != null) tmp.next = null; head.next = node; return result; } // Utility functions // Function to inserts a new // Node at front of the list function push(new_data) { var new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print linked list function printList() { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write(); } /* Driver program to test above functions */ /* * Constructed Linked List is 1->2->3->4->5->6->7->8->null */ push(8); push(7); push(6); push(5); push(4); push(3); push(2); push(1); head = reverse(head, 3); printList(); // This code is contributed by gauravrajput1 </script>
Producción
3 2 1 6 5 4 8 7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)