Reorganice una lista enlazada de tal manera que todos los Nodes de posiciones impares estén juntos y todos los Nodes de posiciones pares estén juntos.
Ejemplos:
Input: 1->2->3->4 Output: 1->3->2->4 Input: 10->22->30->43->56->70 Output: 10->30->56->22->43->70
Lo importante en esta pregunta es asegurarse de que todos los casos a continuación se manejen
- Lista enlazada vacía.
- Una lista enlazada con un solo Node.
- Una lista enlazada con solo dos Nodes.
- Una lista enlazada con un número impar de Nodes.
- Una lista enlazada con un número par de Nodes.
El siguiente programa mantiene dos punteros ‘impar’ y ‘par’ para los Nodes actuales en posiciones pares e impares respectivamente. También almacenamos el primer Node de la lista enlazada par para que podamos adjuntar la lista par al final de la lista impar después de que todos los Nodes pares e impares estén conectados entre sí en dos listas diferentes.
C
// C program to rearrange a linked list in
// such a way that all odd positioned node
// are stored before all even positioned
// nodes
#include<bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node
{
int data;
struct Node* next;
};
// A utility function to create a
// new node
Node* newNode(int key)
{
Node *temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// Rearranges given linked list such that
// all even positioned nodes are before
// odd positioned. Returns new head of
// linked List.
Node *rearrangeEvenOdd(Node *head)
{
// Corner case
if (head == NULL)
return NULL;
// Initialize first nodes of even
// and odd lists
Node *odd = head;
Node *even = head->next;
// Remember the first node of even
// list so that we can connect the
// even list at the end of odd list.
Node *evenFirst = even;
while (1)
{
// If there are no more nodes, then
// connect first node of even list
// to the last node of odd list
if (!odd || !even || !(even->next))
{
odd->next = evenFirst;
break;
}
// Connecting odd nodes
odd->next = even->next;
odd = even->next;
// If there are NO more even
// nodes after current odd.
if (odd->next == NULL)
{
even->next = NULL;
odd->next = evenFirst;
break;
}
// Connecting even nodes
even->next = odd->next;
even = odd->next;
}
return head;
}
// A utility function to print a
// linked list
void printlist(Node * node)
{
while (node != NULL)
{
cout << node->data << "->";
node = node->next;
}
cout << "NULL" << endl;
}
// Driver code
int main(void)
{
Node *head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
cout << "Given Linked List";
printlist(head);
head = rearrangeEvenOdd(head);
cout << "Modified Linked List";
printlist(head);
return 0;
}
Producción:
Given Linked List 1->2->3->4->5->NULL Modified Linked List 1->3->5->2->4->NULL
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
¡Consulte el artículo completo sobre Reorganizar una lista enlazada de modo que todos los Nodes posicionados pares e impares estén juntos 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