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.
Java
// Java program to rearrange a linked list
// in such a way that all odd positioned
// node are stored before all even
// positioned nodes
class GfG {
// Linked List Node
static class Node
{
int data;
Node next;
}
// A utility function to create
// a new node
static 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.
static 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 == 1)
{
// If there are no more nodes,
// then connect first node of even
// list to the last node of odd list
if (odd == null || even == null ||
(even.next) == null)
{
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
static void printlist(Node node)
{
while (node != null)
{
System.out.print(node.data + "->");
node = node.next;
}
System.out.println("NULL") ;
}
// Driver code
public static void main(String[] args)
{
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);
System.out.println("Given Linked List");
printlist(head);
head = rearrangeEvenOdd(head);
System.out.println("Modified Linked List");
printlist(head);
}
}
// This code is contributed by Prerna saini
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