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.
Implementación:
C++
// C++ program to arrange linked list in zigzag fashion
#include <bits/stdc++.h>
using namespace std;
/* Link list Node */
struct Node {
int data;
struct Node* next;
};
// This function distributes the Node in zigzag fashion
void zigZagList(Node* head)
{
// If flag is true, then next node should be greater in
// the desired output.
bool flag = true;
// Traverse linked list starting from head.
Node* current = head;
while (current->next != NULL) {
if (flag) /* "<" relation expected */
{
// 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)
swap(current->data, current->next->data);
}
else /* ">" relation expected */
{
// 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)
swap(current->data, current->next->data);
}
current = current->next;
flag = !flag; /* flip flag for reverse checking */
}
}
/* UTILITY FUNCTIONS */
/* Function to push a Node */
void push(Node** head_ref, int new_data)
{
/* allocate Node */
struct 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_ref);
/* move the head to point to the new Node */
(*head_ref) = new_Node;
}
/* Function to print linked list */
void printList(struct Node* Node)
{
while (Node != NULL) {
printf("%d->", Node->data);
Node = Node->next;
}
printf("NULL");
}
/* Driver program to test above function*/
int main(void)
{
/* Start with the empty list */
struct Node* head = NULL;
// create a list 4 -> 3 -> 7 -> 8 -> 6 -> 2 -> 1
// answer should be -> 3 7 4 8 2 6 1
push(&head, 1);
push(&head, 2);
push(&head, 6);
push(&head, 8);
push(&head, 7);
push(&head, 3);
push(&head, 4);
printf("Given linked list \n");
printList(head);
zigZagList(head);
printf("\nZig Zag Linked list \n");
printList(head);
return (0);
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
C
// C program to arrange linked list in zigzag fashion
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/* Link list Node */
typedef struct Node {
int data;
struct Node* next;
} Node;
// This function swaps values pointed by xp and yp
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// This function distributes the Node in zigzag fashion
void zigZagList(Node* head)
{
// If flag is true, then next node should be greater in
// the desired output.
bool flag = true;
// Traverse linked list starting from head.
Node* current = head;
while (current->next != NULL) {
if (flag) /* "<" relation expected */
{
// 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)
swap(¤t->data, ¤t->next->data);
}
else /* ">" relation expected */
{
// 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)
swap(¤t->data, ¤t->next->data);
}
current = current->next;
flag = !flag; /* flip flag for reverse checking */
}
}
/* UTILITY FUNCTIONS */
/* Function to push a Node */
void push(Node** head_ref, int new_data)
{
/* allocate Node */
struct Node* new_Node = (Node*)malloc(sizeof(Node));
/* put in the data */
new_Node->data = new_data;
/* link the old list off the new Node */
new_Node->next = (*head_ref);
/* move the head to point to the new Node */
(*head_ref) = new_Node;
}
/* Function to print linked list */
void printList(struct Node* Node)
{
while (Node != NULL) {
printf("%d->", Node->data);
Node = Node->next;
}
printf("NULL");
}
/* Driver program to test above function*/
int main(void)
{
/* Start with the empty list */
struct Node* head = NULL;
// create a list 4 -> 3 -> 7 -> 8 -> 6 -> 2 -> 1
// answer should be -> 3 7 4 8 2 6 1
push(&head, 1);
push(&head, 2);
push(&head, 6);
push(&head, 8);
push(&head, 7);
push(&head, 3);
push(&head, 4);
printf("Given linked list \n");
printList(head);
zigZagList(head);
printf("\nZig Zag Linked list \n");
printList(head);
return (0);
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
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) {
if (flag == true) /* "<" relation expected */
{
/* 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;
}
}
else /* ">" relation expected */
{
/* 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.
Python
# Python code to rearrange linked list in zig zag fashion
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
# This function distributes the Node in zigzag fashion
def zigZagList(head):
# If flag is true, then next node should be greater
# in the desired output.
flag = True
# Traverse linked list starting from head.
current = head
while (current.next != None):
if (flag): # "<" relation expected
# 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):
t = current.data
current.data = current.next.data
current.next.data = t
else :# ">" relation expected
# 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):
t = current.data
current.data = current.next.data
current.next.data = t
current = current.next
if(flag):
flag = False # flip flag for reverse checking
else:
flag = True
return head
# function to insert a Node in
# the linked list at the beginning.
def push(head, k):
tem = Node(0)
tem.data = k
tem.next = head
head = tem
return head
# function to display Node of linked list.
def display( head):
curr = head
while (curr != None):
print( curr.data, "->", end =" ")
curr = curr.next
print("None")
# Driver code
head = None
# create a list 4 -> 3 -> 7 -> 8 -> 6 -> 2 -> 1
# answer should be -> 3 7 4 8 2 6 1
head = push(head, 1)
head = push(head, 2)
head = push(head, 6)
head = push(head, 8)
head = push(head, 7)
head = push(head, 3)
head = push(head, 4)
print("Given linked list \n")
display(head)
head = zigZagList(head)
print("\nZig Zag Linked list \n")
display(head)
# This code is contributed by Arnab Kundu
C#
// C# program to arrange
// linked list in zigzag fashion
using System;
class GfG {
/* Link list Node */
class Node {
public int data;
public 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.
bool flag = true;
// Traverse linked list starting from head.
Node current = head;
while (current != null && current.next != null) {
if (flag == true) /* "<" relation expected */
{
/* 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 != null && current.next != null && current.data > current.next.data) {
temp = current.data;
current.data = current.next.data;
current.next.data = temp;
}
}
else /* ">" relation expected */
{
/* 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 != null && current.next != null && 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) {
Console.Write(Node.data + "->");
Node = Node.next;
}
Console.WriteLine("NULL");
}
/* Driver code*/
public static void Main()
{
/* 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);
Console.WriteLine("Given linked list ");
printList(head);
zigZagList(head);
Console.WriteLine("Zig Zag Linked list ");
printList(head);
}
}
/* This code is contributed PrinciRaj1992 */
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) {
if (flag == true) /* "<" relation expected */
{
/*
* 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;
}
} else /* ">" relation expected */
{
/*
* 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 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
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.
Implementación:
C++
// C++ program to arrange linked list
// in zigzag fashion
#include <iostream>
using namespace std;
// a linked list node
struct node {
int data;
node* next;
};
/* Function to push a Node */
void push(node** head_ref, int new_data)
{
node* new_Node = (node*)malloc(sizeof(node));
new_Node->data = new_data;
new_Node->next = (*head_ref);
(*head_ref) = new_Node;
}
// Rearrange the linked list in zig zag way
node* zigzag(node* head, bool flag)
{
if (!head || !head->next)
return head;
if (flag == 1) {
if (head->data > head->next->data)
swap(head->data, head->next->data);
return zigzag(head->next, !flag);
}
else {
if (head->data < head->next->data)
swap(head->data, head->next->data);
return zigzag(head->next, !flag);
}
}
// fun to print list
void printList(node* head)
{
while (head) {
cout << head->data << "-> ";
head = head->next;
}
cout << "NULL";
}
// main fun
int main()
{
node* head = NULL;
push(&head, 10);
push(&head, 5);
push(&head, 20);
push(&head, 15);
push(&head, 11);
printList(head);
cout << endl;
zigzag(head, 1);
cout << "LL in zig zag fashion : " << endl;
printList(head);
return 0;
}
// This code is contributed by Upendra
C
// C program to arrange linked list in zigzag fashion
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// a linked list node
typedef struct node {
int data;
struct node* next;
} node;
void push(node** head_ref, int new_data)
{
node* new_Node = (node*)malloc(sizeof(node));
new_Node->data = new_data;
new_Node->next = (*head_ref);
(*head_ref) = new_Node;
}
// function to swap the elements
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// Rearrange the linked list in zig zag way
node* zigzag(node* head, bool flag)
{
if (!head || !head->next)
return head;
if (flag == 1) {
if (head->data > head->next->data)
swap(&head->data, &head->next->data);
return zigzag(head->next, !flag);
}
else {
if (head->data < head->next->data)
swap(&head->data, &head->next->data);
return zigzag(head->next, !flag);
}
}
// fun to print list
void printList(node* head)
{
while (head) {
printf("%d-> ", head->data);
head = head->next;
}
printf("NULL");
}
// main fun
int main()
{
node* head = NULL;
push(&head, 10);
push(&head, 5);
push(&head, 20);
push(&head, 15);
push(&head, 11);
printList(head);
printf("\n");
zigzag(head, 1);
printf("LL in zig zag fashion : \n");
printList(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
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();
}
}
Python3
# Python program for the above approach// Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
head = None
# Print Linked List
def printLL():
t = head
while (t != None):
print(t.data, end=" ->")
t = t.next
print()
# Swap both nodes
def swap(a, b):
if(a == None or b == None):
return
temp = a.data
a.data = b.data
b.data = temp
# Rearrange the linked list
# in zig zag way
def zigZag(node, flag):
if(node == None or node.next == None):
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 = Node(11)
head.next = Node(15)
head.next.next = Node(20)
head.next.next.next = Node(5)
head.next.next.next.next = Node(10)
printLL()
# 0 means the current element
# should be smaller than the next
flag = 0
zigZag(head, flag)
print("LL in zig zag fashion : ")
printLL()
# This code is contributed by avanitrachhadiya2155.
C#
// C# program for the above approach
using System;
// Node class
public class Node {
public int data;
public Node next;
public
Node(int data)
{
this.data = data;
}
}
public class GFG {
private Node head;
// Print Linked List
public void printLL()
{
Node t = head;
while (t != null) {
Console.Write(t.data + " ->");
t = t.next;
}
Console.WriteLine();
}
// 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);
Console.WriteLine("LL in zig zag fashion : ");
lobj.printLL();
}
}
// This code is contributed by umadevi9616
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 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) estructura de datos de espacio adicional para almacenar valores.
Este artículo es una contribución de Utkarsh Trivedi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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