Dada una lista enlazada, la tarea es invertir los elementos pares contiguos e imprimir la lista enlazada actualizada.
Entrada: 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 8 -> 5 -> NULL
Salida: 1 2 3 3 8 6 4 5
Lista inicial: 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 8 -> 5 -> NULL
Lista invertida: 1 -> 2 -> 3 -> 3 -> 8 -> 6 -> 4 -> 5 -> NULL
Entrada: 11 -> 32 – > 7 -> NULL
Salida: 11 32 7
Planteamiento: La inversión de los elementos pares contiguos no tendrá lugar cuando:
- El valor del Node es impar.
- El valor del Node es par pero los valores adyacentes son impares.
En el resto de los casos, el bloque continuo de Nodes pares puede invertirse.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Structure of a node of the linked list
struct node {
int data;
struct node* next;
};
// Function to create a new node
struct node* newNode(int d)
{
struct node* newnode = new node();
newnode->data = d;
newnode->next = NULL;
return newnode;
}
// Recursive function to reverse the consecutive
// even nodes of the linked list
struct node* reverse(struct node* head, struct node* prev)
{
// Base case
if (head == NULL)
return NULL;
struct node* temp;
struct node* curr;
curr = head;
// Reversing nodes until curr node's value
// turn odd or Linked list is fully traversed
while (curr != NULL && curr->data % 2 == 0) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
// If elements were reversed then head
// pointer needs to be changed
if (curr != head) {
head->next = curr;
// Recur for the remaining linked list
curr = reverse(curr, NULL);
return prev;
}
// Simply iterate over the odd value nodes
else {
head->next = reverse(head->next, head);
return head;
}
}
// Utility function to print the
// contents of the linked list
void printLinkedList(struct node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 3, 4, 6, 8, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
struct node* head = NULL;
struct node* p;
// Constructing linked list
for (int i = 0; i < n; i++) {
if (head == NULL) {
p = newNode(arr[i]);
head = p;
continue;
}
p->next = newNode(arr[i]);
p = p->next;
}
// Head of the updated linked list
head = reverse(head, NULL);
// Printing the reversed linked list
printLinkedList(head);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Structure of a node of the linked list
static class node
{
int data;
node next;
};
// Function to create a new node
static node newNode(int d)
{
node newnode = new node();
newnode.data = d;
newnode.next = null;
return newnode;
}
// Recursive function to reverse the consecutive
// even nodes of the linked list
static node reverse(node head, node prev)
{
// Base case
if (head == null)
return null;
node temp;
node curr;
curr = head;
// Reversing nodes until curr node's value
// turn odd or Linked list is fully traversed
while (curr != null && curr.data % 2 == 0)
{
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// If elements were reversed then head
// pointer needs to be changed
if (curr != head)
{
head.next = curr;
// Recur for the remaining linked list
curr = reverse(curr, null);
return prev;
}
// Simply iterate over the odd value nodes
else
{
head.next = reverse(head.next, head);
return head;
}
}
// Utility function to print the
// contents of the linked list
static void printLinkedList(node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 3, 4, 6, 8, 5 };
int n = arr.length;
node head = null;
node p = new node();
// Constructing linked list
for (int i = 0; i < n; i++)
{
if (head == null)
{
p = newNode(arr[i]);
head = p;
continue;
}
p.next = newNode(arr[i]);
p = p.next;
}
// Head of the updated linked list
head = reverse(head, null);
// Printing the reversed linked list
printLinkedList(head);
}
}
// This code is contributed by PrinciRaj1992
C#
// C# implementation of the above approach
using System;
class GFG
{
// Structure of a node of the linked list
public class node
{
public int data;
public node next;
};
// Function to create a new node
static node newNode(int d)
{
node newnode = new node();
newnode.data = d;
newnode.next = null;
return newnode;
}
// Recursive function to reverse the consecutive
// even nodes of the linked list
static node reverse(node head, node prev)
{
// Base case
if (head == null)
return null;
node temp;
node curr;
curr = head;
// Reversing nodes until curr node's value
// turn odd or Linked list is fully traversed
while (curr != null && curr.data % 2 == 0)
{
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// If elements were reversed then head
// pointer needs to be changed
if (curr != head)
{
head.next = curr;
// Recur for the remaining linked list
curr = reverse(curr, null);
return prev;
}
// Simply iterate over the odd value nodes
else
{
head.next = reverse(head.next, head);
return head;
}
}
// Utility function to print the
// contents of the linked list
static void printLinkedList(node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 3, 4, 6, 8, 5 };
int n = arr.Length;
node head = null;
node p = new node();
// Constructing linked list
for (int i = 0; i < n; i++)
{
if (head == null)
{
p = newNode(arr[i]);
head = p;
continue;
}
p.next = newNode(arr[i]);
p = p.next;
}
// Head of the updated linked list
head = reverse(head, null);
// Printing the reversed linked list
printLinkedList(head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Structure of a node of the linked list
class node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to create a new node
function newNode( d)
{
var newnode = new node();
newnode.data = d;
newnode.next = null;
return newnode;
}
// Recursive function to reverse the consecutive
// even nodes of the linked list
function reverse(head, prev)
{
// Base case
if (head == null)
return null;
var temp;
var curr;
curr = head;
// Reversing nodes until curr node's value
// turn odd or Linked list is fully traversed
while (curr != null && curr.data % 2 == 0)
{
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// If elements were reversed then head
// pointer needs to be changed
if (curr != head)
{
head.next = curr;
// Recur for the remaining linked list
curr = reverse(curr, null);
return prev;
}
// Simply iterate over the odd value nodes
else
{
head.next = reverse(head.next, head);
return head;
}
}
// Utility function to print the
// contents of the linked list
function printLinkedList( head)
{
while (head != null)
{
document.write(head.data + " ");
head = head.next;
}
}
// Driver Code
let arr = [ 1, 2, 3, 3, 4, 6, 8, 5 ];
let n = arr.length;
var head = null;
var p = new node();
// Constructing linked list
for (let i = 0; i < n; i++)
{
if (head == null)
{
p = newNode(arr[i]);
head = p;
continue;
}
p.next = newNode(arr[i]);
p = p.next;
}
// Head of the updated linked list
head = reverse(head, null);
// Printing the reversed linked list
printLinkedList(head);
// This code is contributed by jana_sayantan.
</script>
Producción:
1 2 3 3 8 6 4 5
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por cr7_bullet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA