Dada una lista enlazada A[] de N enteros, la tarea es invertir el orden de todos los enteros en una posición par.
Ejemplos:
Entrada: A[] = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Salida: 1 6 3 4 5 2
Explicación: Los Nodes en posiciones pares en la lista enlazada dada son 2, 4 y 6 Entonces, después de invertir el orden, la nueva lista enlazada será 1 -> 6 -> 3 -> 4 -> 5 -> 2 -> NULL.Entrada: A[] = 1 -> 5 -> 3->NULL
Salida: 1 5 3
Enfoque: El problema dado se puede resolver manteniendo dos listas enlazadas , una lista para todos los Nodes en posiciones impares y otra lista para todos los Nodes en posiciones pares. Atraviese la lista enlazada dada que se considerará como la lista impar. Por lo tanto, para todos los Nodes en posiciones pares, elimínelos de la lista impar e insértelos al principio de la lista de Nodes pares. Dado que los Nodes se agregan al frente , su orden se invertirá. Combine las dos listas en posiciones alternativas, que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Node of the linked list
class Node {
public:
int data;
Node* next;
};
// Function to reverse all the even
// positioned node of given linked list
Node* reverse_even(Node* A)
{
// Stores the nodes with
// even positions
Node* even = NULL;
// Stores the nodes with
// odd positions
Node* odd = A;
// If size of list is less that
// 3, no change is required
if (!odd || !odd->next || !odd->next->next)
return odd;
// Loop to traverse the list
while (odd && odd->next) {
// Store the even positioned
// node in temp
Node* temp = odd->next;
odd->next = temp->next;
// Add the even node to the
// beginning of even list
temp->next = even;
// Make temp as new even list
even = temp;
// Move odd to it's next node
odd = odd->next;
}
odd = A;
// Merge the evenlist into
// odd list alternatively
while (even) {
// Stores the even's next
// node in temp
Node* temp = even->next;
// Link the next odd node
// to next of even node
even->next = odd->next;
// Link even to next odd node
odd->next = even;
// Make new even as temp node
even = temp;
// Move odd to it's 2nd next node
odd = odd->next->next;
}
return A;
}
// Function to add a node at
// the beginning of Linked List
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to print nodes
// in a given linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Driver Code
int main()
{
Node* start = NULL;
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
start = reverse_even(start);
printList(start);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Node of the linked list
static class Node {
int data;
Node next;
};
static Node start = null;
// Function to reverse all the even
// positioned node of given linked list
static Node reverse_even(Node A)
{
// Stores the nodes with
// even positions
Node even = null;
// Stores the nodes with
// odd positions
Node odd = A;
// If size of list is less that
// 3, no change is required
if (odd==null || odd.next==null || odd.next.next==null)
return odd;
// Loop to traverse the list
while (odd!=null && odd.next!=null) {
// Store the even positioned
// node in temp
Node temp = odd.next;
odd.next = temp.next;
// Add the even node to the
// beginning of even list
temp.next = even;
// Make temp as new even list
even = temp;
// Move odd to it's next node
odd = odd.next;
}
odd = A;
// Merge the evenlist into
// odd list alternatively
while (even!=null) {
// Stores the even's next
// node in temp
Node temp = even.next;
// Link the next odd node
// to next of even node
even.next = odd.next;
// Link even to next odd node
odd.next = even;
// Make new even as temp node
even = temp;
// Move odd to it's 2nd next node
odd = odd.next.next;
}
return A;
}
// Function to add a node at
// the beginning of Linked List
static void push(int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = start;
start = new_node;
}
// Function to print nodes
// in a given linked list
static void printList(Node node)
{
while (node != null) {
System.out.print(node.data+ " ");
node = node.next;
}
}
// Driver Code
public static void main(String[] args)
{
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
start = reverse_even(start);
printList(start);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach start = None # Node of the linked list class Node: def __init__(self, data): self.data = data self.next = None # Function to reverse all the even # positioned node of given linked list def reverse_even(A): # Stores the nodes with # even positions even = None # Stores the nodes with # odd positions odd = A # If size of list is less that # 3, no change is required if (odd == None or odd.next == None or odd.next.next == None): return odd # Loop to traverse the list while (odd and odd.next): # Store the even positioned # node in temp temp = odd.next odd.next = temp.next # Add the even node to the # beginning of even list temp.next = even # Make temp as new even list even = temp # Move odd to it's next node odd = odd.next odd = A # Merge the evenlist into # odd list alternatively while (even): # Stores the even's next # node in temp temp = even.next # Link the next odd node # to next of even node even.next = odd.next # Link even to next odd node odd.next = even # Make new even as temp node even = temp # Move odd to it's 2nd next node odd = odd.next.next return A # Function to add a node at # the beginning of Linked List def push(new_data): global start new_node = Node(new_data) new_node.next = start start = new_node # Function to print nodes # in a given linked list def printList(node): while (node != None): print(node.data, end=" ") node = node.next # Driver Code start = None push(6) push(5) push(4) push(3) push(2) push(1) start = reverse_even(start) printList(start) # This code is contributed by saurabh_jaiswal.
C#
// C# program for the above approach
using System;
public class GFG{
// Node of the linked list
class Node {
public int data;
public Node next;
};
static Node start = null;
// Function to reverse all the even
// positioned node of given linked list
static Node reverse_even(Node A)
{
// Stores the nodes with
// even positions
Node even = null;
// Stores the nodes with
// odd positions
Node odd = A;
// If size of list is less that
// 3, no change is required
if (odd==null || odd.next==null || odd.next.next==null)
return odd;
// Loop to traverse the list
while (odd!=null && odd.next!=null) {
// Store the even positioned
// node in temp
Node temp = odd.next;
odd.next = temp.next;
// Add the even node to the
// beginning of even list
temp.next = even;
// Make temp as new even list
even = temp;
// Move odd to it's next node
odd = odd.next;
}
odd = A;
// Merge the evenlist into
// odd list alternatively
while (even!=null) {
// Stores the even's next
// node in temp
Node temp = even.next;
// Link the next odd node
// to next of even node
even.next = odd.next;
// Link even to next odd node
odd.next = even;
// Make new even as temp node
even = temp;
// Move odd to it's 2nd next node
odd = odd.next.next;
}
return A;
}
// Function to add a node at
// the beginning of Linked List
static void push(int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = start;
start = new_node;
}
// Function to print nodes
// in a given linked list
static void printList(Node node)
{
while (node != null) {
Console.Write(node.data+ " ");
node = node.next;
}
}
// Driver Code
public static void Main(String[] args)
{
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
start = reverse_even(start);
printList(start);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Node of the linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
};
// Function to reverse all the even
// positioned node of given linked list
function reverse_even(A) {
// Stores the nodes with
// even positions
let even = null;
// Stores the nodes with
// odd positions
let odd = A;
// If size of list is less that
// 3, no change is required
if (odd == null || odd.next == null || odd.next.next == null)
return odd;
// Loop to traverse the list
while (odd && odd.next) {
// Store the even positioned
// node in temp
let temp = odd.next;
odd.next = temp.next;
// Add the even node to the
// beginning of even list
temp.next = even;
// Make temp as new even list
even = temp;
// Move odd to it's next node
odd = odd.next;
}
odd = A;
// Merge the evenlist into
// odd list alternatively
while (even) {
// Stores the even's next
// node in temp
let temp = even.next;
// Link the next odd node
// to next of even node
even.next = odd.next;
// Link even to next odd node
odd.next = even;
// Make new even as temp node
even = temp;
// Move odd to it's 2nd next node
odd = odd.next.next;
}
return A;
}
// Function to add a node at
// the beginning of Linked List
function push(new_data) {
let new_node = new Node();
new_node.data = new_data;
new_node.next = start;
start = new_node;
}
// Function to print nodes
// in a given linked list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Driver Code
let start = null;
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
start = reverse_even(start);
printList(start);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
1 6 3 4 5 2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nirajgusain5 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA