Dada una lista enlazada, reorganícela de modo que la lista convertida tenga la forma a < b > c < d > e < f… donde a, b, c… son Nodes de datos consecutivos de la lista enlazada.
Ejemplos:
Input: 1->2->3->4
Output: 1->3->2->4
Explanation: 1 and 3 should come first before 2 and 4 in
zig-zag fashion, So resultant linked-list
will be 1->3->2->4.
Input: 11->15->20->5->10
Output: 11->20->5->15->10
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Un enfoque simple para hacer esto es ordenar la lista enlazada usando la ordenación por combinación y luego intercambiar alternativamente, pero eso requiere una complejidad de tiempo O(n Log n). Aquí n es un número de elementos en la lista enlazada.
Un enfoque eficiente que requiere tiempo O(n) es usar un solo escaneo similar a la ordenación de burbujas y luego mantener una bandera para representar en qué orden() estamos actualmente. Si los dos elementos actuales no están en ese orden, intercambie esos elementos, de lo contrario no. Consulte esto para obtener una explicación detallada de la orden de intercambio.
Java
// Java program to arrange linked
// list in zigzag fashion
class GfG
{
// Link list Node
static class Node
{
int data;
Node next;
}
static Node head = null;
static int temp = 0;
// This function distributes
// the Node in zigzag fashion
static void zigZagList(Node head)
{
// If flag is true, then
// next node should be greater
// in the desired output.
boolean flag = true;
// Traverse linked list starting
// from head.
Node current = head;
while (current != null &&
current.next != null)
{
// "<" relation expected
if (flag == true)
{
/* If we have a situation like
A > B > C where A, B and C
are consecutive Nodes in list
we get A > B < C by swapping B
and C */
if (current.data > current.next.data)
{
temp = current.data;
current.data = current.next.data;
current.next.data = temp;
}
}
// ">" relation expected
else
{
/* If we have a situation like
A < B < C where A, B and C
are consecutive Nodes in list
we get A < C > B by swapping
B and C */
if (current.data < current.next.data)
{
temp = current.data;
current.data = current.next.data;
current.next.data = temp;
}
}
current = current.next;
// flip flag for reverse checking
flag = !(flag);
}
}
// UTILITY FUNCTIONS
// Function to push a Node
static void push(int new_data)
{
// Allocate Node
Node new_Node = new Node();
// Put in the data
new_Node.data = new_data;
// Link the old list off the
// new Node
new_Node.next = (head);
// Move the head to point to
// the new Node
(head) = new_Node;
}
// Function to print 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)
{
// Start with the empty list
// Node head = null;
// create a list 4 -> 3 -> 7 ->
// 8 -> 6 -> 2 -> 1
// answer should be -> 3 7 4 8
// 2 6 1
push(1);
push(2);
push(6);
push(8);
push(7);
push(3);
push(4);
System.out.println(
"Given linked list ");
printList(head);
zigZagList(head);
System.out.println(
"Zig Zag Linked list ");
printList(head);
}
}
// This code is contributed by Prerna Saini.
Producción:
Given linked list 4->3->7->8->6->2->1->NULL Zig Zag Linked list 3->7->4->8->2->6->1->NULL
Otro enfoque:
en el código anterior, la función de empuje empuja el Node al frente de la lista vinculada, el código se puede modificar fácilmente para empujar el Node al final de la lista. Otra cosa a tener en cuenta es que el intercambio de datos entre dos Nodes se realiza intercambiando por valor, no intercambiando por enlaces para simplificar, para la técnica de intercambio por enlaces, consulte this .
Esto también se puede hacer recursivamente. La idea sigue siendo la misma, supongamos que el valor de la bandera determina la condición que necesitamos verificar para comparar el elemento actual. Entonces, si el indicador es 0 (o falso), el elemento actual debe ser más pequeño que el siguiente y si el indicador es 1 (o verdadero), entonces el elemento actual debe ser mayor que el siguiente. Si no, intercambie los valores de los Nodes.
Java
// Java program for the above approach
import java.io.*;
// Node class
class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
}
}
public class GFG
{
private Node head;
// Print Linked List
public void printLL()
{
Node t = head;
while (t != null)
{
System.out.print(t.data +
" ->");
t = t.next;
}
System.out.println();
}
// Swap both nodes
public void swap(Node a,
Node b)
{
if (a == null || b == null)
return;
int temp = a.data;
a.data = b.data;
b.data = temp;
}
// Rearrange the linked list
// in zig zag way
public Node zigZag(Node node,
int flag)
{
if (node == null ||
node.next == null)
{
return node;
}
if (flag == 0)
{
if (node.data >
node.next.data)
{
swap(node, node.next);
}
return zigZag(node.next, 1);
}
else
{
if (node.data <
node.next.data)
{
swap(node, node.next);
}
return zigZag(node.next, 0);
}
}
// Driver Code
public static void main(String[] args)
{
GFG lobj = new GFG();
lobj.head = new Node(11);
lobj.head.next = new Node(15);
lobj.head.next.next =
new Node(20);
lobj.head.next.next.next =
new Node(5);
lobj.head.next.next.next.next =
new Node(10);
lobj.printLL();
// 0 means the current element
// should be smaller than the next
int flag = 0;
lobj.zigZag(lobj.head, flag);
System.out.println(
"LL in zig zag fashion : ");
lobj.printLL();
}
}
Producción:
11 ->15 ->20 ->5 ->10 -> LL in zig zag fashion : 11 ->20 ->5 ->15 ->10 ->
Análisis de Complejidad:
- Complejidad temporal: O(n).
El recorrido de la lista se realiza una sola vez y tiene ‘n’ elementos. - Espacio Auxiliar: O(n).
O(n) espacio adicional debido a la pila recursiva.
Consulte el artículo completo sobre Reorganizar una lista vinculada en forma de zig-zag 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