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.
Javascript
<script>
// Javascript program to arrange
// linked list in zigzag fashion
// Link list Node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
var head = null;
var temp = 0;
// This function distributes
// the Node in zigzag fashion
function zigZagList(head)
{
// If flag is true, then
// next node should be greater
// in the desired output.
var flag = true;
// Traverse linked list starting from
// head.
var 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
Function push(new_data)
{
// Allocate Node
var 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
function printList(node)
{
while (node != null)
{
document.write(node.data + "->");
node = node.next;
}
document.write("NULL<br/>");
}
// Driver code
// 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);
document.write(
"Given linked list <br/>");
printList(head);
zigZagList(head);
document.write(
"Zig Zag Linked list <br/>");
printList(head);
// This code is contributed by gauravrajput1
</script>
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
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos usando espacio extra.
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.
Javascript
<script>
// Javascript program for the
// above approach
// Node class
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
var head;
// Print Linked List
function printLL()
{
var t = head;
while (t != null)
{
document.write(t.data +
" ->");
t = t.next;
}
document.write();
}
// Swap both nodes
function swap(a, b)
{
if (a == null ||
b == null)
return;
var temp = a.data;
a.data = b.data;
b.data = temp;
}
// Rearrange the linked list
// in zig zag way
function zigZag(node, 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
head = new Node(11);
head.next = new Node(15);
head.next.next = new Node(20);
head.next.next.next = new Node(5);
head.next.next.next.next =
new Node(10);
printLL();
// 0 means the current element
// should be smaller than the next
var flag = 0;
zigZag(head, flag);
document.write(
"<br/>LL in zig zag fashion : <br/>");
printLL();
// This code is contributed by umadevi9616
</script>
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 extra debido a llamadas recursivas
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