Dada una lista enlazada individualmente que contiene n Nodes. Modifique el valor de los Nodes de la primera mitad de modo que el nuevo valor del primer Node sea igual al valor del último Node menos el valor actual del primer Node, el nuevo valor del segundo Node sea igual al valor del penúltimo Node menos el valor actual del segundo Node, del mismo modo para los Nodes de la primera mitad. Si n es impar, el valor del Node central permanece sin cambios.
Ejemplos:
Entrada: 10 -> 4 -> 5 -> 3 -> 6
Salida: -4 -> -1 -> 5 -> 3 -> 6
Entrada: 2 -> 9 -> 8 -> 12 -> 7 -> 10
Salida: 8 -> -2 -> 4 -> 12 -> 7 -> 10
Enfoque: Atraviese la lista de enlaces utilizando la recursividad solo para la segunda mitad de la lista en lugar de repetir toda la lista, lo que reduce el marco de la pila. Con base en el número de Nodes en la lista, calculamos el punto de partida para la segunda mitad de la lista y la lista se repite para la segunda mitad. Una vez que la segunda mitad se repite por completo, se resta el valor del Node presente en la pila y el valor del Node actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to modify the contents
// of the linked list with recursion
#include <bits/stdc++.h>
using namespace std;
// Represents a Node of the linked list
struct Node {
int data;
Node* next;
};
// Function to create and return a new node
Node* insert(int data)
{
Node* temp;
temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function which returns the total number of
// node present in the list
int getTotalNodeCount(Node* head)
{
int totalNodesCount = 0;
while(head != NULL)
{
totalNodesCount++;
head = head->next;
}
return totalNodesCount;
}
// Function to modify the contents
// of the given linked lists
void modifyContents(Node** first_half ,
Node* second_half)
{
if (second_half == NULL)
{
return;
}
modifyContents(first_half,second_half->next);
(*first_half)->data = second_half->data - (*first_half)->data;
(*first_half) = (*first_half)->next;
return;
}
// Wrapper function which calculates the starting
// point for second half of the list
void modifyContentsWrapper(Node** head)
{
Node *ptr = NULL; // pointer to second half of list
Node *temp = NULL;
int diff = 0;
int length = 0; // number of nodes in the list
if (*head == NULL)
{
return;
}
length = getTotalNodeCount(*head);
// If link list has odd number of nodes, then pointer
// for second half starts from (length of link list + 1).
// Say for an example, for the list 10->4->5->3->6 pointer
// should start from 3.
// If list has even number of nodes, 10->4->5->9->6->8,
// pointer starts from 9.
diff = (length%2 == 0? (length/2) :(length/2)+1 );
ptr = *head;
while(diff--)
ptr = ptr->next;
temp = *head;
modifyContents(&temp,ptr);
return;
}
// Function to print the contents of the linked list
void print(Node* nod)
{
if (nod == NULL) {
return;
}
cout << nod->data;
if (nod->next != NULL)
cout << " -> ";
print(nod->next);
}
// Driver code
int main()
{
Node* head = insert(2);
head->next = insert(9);
head->next->next = insert(8);
head->next->next->next = insert(12);
head->next->next->next->next = insert(7);
head->next->next->next->next->next = insert(10);
// Modify the linked list
modifyContentsWrapper(&head);
// Print the modified linked list
print(head);
return 0;
}
Java
// Java program to modify the contents
// of the linked list with recursion
class GFG
{
// Represents a Node of the linked list
static class Node
{
int data;
Node next;
};
// Function to create and return a new node
static Node insert(int data)
{
Node temp;
temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function which returns the total number
// of node present in the list
static int getTotalNodeCount(Node head)
{
int totalNodesCount = 0;
while(head != null)
{
totalNodesCount++;
head = head.next;
}
return totalNodesCount;
}
static Node temp = null;
// Function to modify the contents
// of the given linked lists
static void modifyContents(Node second_half)
{
if (second_half == null)
{
return;
}
modifyContents(second_half.next);
(temp).data = second_half.data - (temp).data;
(temp) = (temp).next;
return;
}
// Wrapper function which calculates the starting
// point for second half of the list
static Node modifyContentsWrapper(Node head)
{
Node ptr = null; // pointer to second half of list
temp = null;
int diff = 0;
int length = 0; // number of nodes in the list
if (head == null)
{
return null;
}
length = getTotalNodeCount(head);
// If link list has odd number of nodes,
// then pointer for second half starts
// from (length of link list + 1).
// Say for an example, for the list 10.4.5.3.6
// pointer should start from 3.
// If list has even number of nodes,
// 10.4.5.9.6.8, pointer starts from 9.
diff = (length % 2 == 0 ?
(length / 2) : (length / 2) + 1);
ptr = head;
while(diff-->0)
ptr = ptr.next;
temp = head;
modifyContents(ptr);
return head;
}
// Function to print the contents
// of the linked list
static void print(Node nod)
{
if (nod == null)
{
return;
}
System.out.print( nod.data);
if (nod.next != null)
System.out.print( " -> ");
print(nod.next);
}
// Driver code
public static void main(String args[])
{
Node head = insert(2);
head.next = insert(9);
head.next.next = insert(8);
head.next.next.next = insert(12);
head.next.next.next.next = insert(7);
head.next.next.next.next.next = insert(10);
// Modify the linked list
head = modifyContentsWrapper(head);
// Print the modified linked list
print(head);
}
}
// This code is contributed by Arnab Kundu
Python
# Python program to modify the contents # of the linked list with recursion # Represents a Node of the linked list class Node: def __init__(self, data): self.data = data self.next = None # Function to create and return a new node def insert( data) : temp = Node(0) temp.data = data temp.next = None return temp # Function which returns the total number # of node present in the list def getTotalNodeCount( head) : totalNodesCount = 0 while(head != None): totalNodesCount = totalNodesCount + 1 head = head.next return totalNodesCount temp = None # Function to modify the contents # of the given linked lists def modifyContents( second_half) : if (second_half == None): return global temp modifyContents(second_half.next) (temp).data = second_half.data - (temp).data (temp) = (temp).next return # Wrapper function which calculates the starting # point for second half of the list def modifyContentsWrapper(head) : # pointer to second half of list ptr = None diff = 0 # number of nodes in the list length = 0 global temp temp = None if (head == None) : return None length = getTotalNodeCount(head) # If link list has odd number of nodes, # then pointer for second half starts # from (length of link list + 1). # Say for an example, for the list 10.4.5.3.6 # pointer should start from 3. # If list has even number of nodes, # 10.4.5.9.6.8, pointer starts from 9. if(length % 2 == 0): diff = (length / 2) else: diff = (length / 2) + 1 ptr = head while(diff > 0): diff = diff - 1 ptr = ptr.next temp = head modifyContents(ptr) return head # Function to print the contents # of the linked list def print_(nod): if (nod == None) : return print(nod.data, end = " ") if (nod.next != None): print( " -> ",end = "") print_(nod.next) # Driver code head = insert(2) head.next = insert(9) head.next.next = insert(8) head.next.next.next = insert(12) head.next.next.next.next = insert(7) head.next.next.next.next.next = insert(10) # Modify the linked list head = modifyContentsWrapper(head) # Print the modified linked list print_(head) # This code is contributed by Arnab Kundu
C#
// C# program to modify the contents
// of the linked list with recursion
using System;
class GFG
{
// Represents a Node of the linked list
public class Node
{
public int data;
public Node next;
};
// Function to create and return a new node
static Node insert(int data)
{
Node temp;
temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function which returns the total number
// of node present in the list
static int getTotalNodeCount(Node head)
{
int totalNodesCount = 0;
while(head != null)
{
totalNodesCount++;
head = head.next;
}
return totalNodesCount;
}
static Node temp = null;
// Function to modify the contents
// of the given linked lists
static void modifyContents(Node second_half)
{
if (second_half == null)
{
return;
}
modifyContents(second_half.next);
(temp).data = second_half.data - (temp).data;
(temp) = (temp).next;
return;
}
// Wrapper function which calculates the starting
// point for second half of the list
static Node modifyContentsWrapper(Node head)
{
// pointer to second half of list
Node ptr = null;
temp = null;
int diff = 0;
// number of nodes in the list
int length = 0;
if (head == null)
{
return null;
}
length = getTotalNodeCount(head);
// If link list has odd number of nodes,
// then pointer for second half starts
// from (length of link list + 1).
// Say for an example, for the list 10.4.5.3.6
// pointer should start from 3.
// If list has even number of nodes,
// 10.4.5.9.6.8, pointer starts from 9.
diff = (length % 2 == 0 ?
(length / 2) : (length / 2) + 1);
ptr = head;
while(diff-->0)
ptr = ptr.next;
temp = head;
modifyContents(ptr);
return head;
}
// Function to print the contents
// of the linked list
static void print(Node nod)
{
if (nod == null)
{
return;
}
Console.Write(nod.data);
if (nod.next != null)
Console.Write(" -> ");
print(nod.next);
}
// Driver code
public static void Main(String []args)
{
Node head = insert(2);
head.next = insert(9);
head.next.next = insert(8);
head.next.next.next = insert(12);
head.next.next.next.next = insert(7);
head.next.next.next.next.next = insert(10);
// Modify the linked list
head = modifyContentsWrapper(head);
// Print the modified linked list
print(head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to modify the contents
// of the linked list with recursion
// Represents a Node of the linked list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to create and return a new node
function insert(data) {
var temp;
temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function which returns the total number
// of node present in the list
function getTotalNodeCount(head) {
var totalNodesCount = 0;
while (head != null) {
totalNodesCount++;
head = head.next;
}
return totalNodesCount;
}
var temp = null;
// Function to modify the contents
// of the given linked lists
function modifyContents(second_half) {
if (second_half == null) {
return;
}
modifyContents(second_half.next);
temp.data = second_half.data - temp.data;
temp = temp.next;
return;
}
// Wrapper function which calculates the starting
// point for second half of the list
function modifyContentsWrapper(head) {
// pointer to second half of list
var ptr = null;
temp = null;
var diff = 0;
// number of nodes in the list
var length = 0;
if (head == null) {
return null;
}
length = getTotalNodeCount(head);
// If link list has odd number of nodes,
// then pointer for second half starts
// from (length of link list + 1).
// Say for an example, for the list 10.4.5.3.6
// pointer should start from 3.
// If list has even number of nodes,
// 10.4.5.9.6.8, pointer starts from 9.
diff =
length % 2 == 0 ?
parseInt(length / 2) : parseInt(length / 2) + 1;
ptr = head;
while (diff-- > 0) ptr = ptr.next;
temp = head;
modifyContents(ptr);
return head;
}
// Function to print the contents
// of the linked list
function print(nod) {
if (nod == null) {
return;
}
document.write(nod.data);
if (nod.next != null) document.write(" -> ");
print(nod.next);
}
// Driver code
var head = insert(2);
head.next = insert(9);
head.next.next = insert(8);
head.next.next.next = insert(12);
head.next.next.next.next = insert(7);
head.next.next.next.next.next = insert(10);
// Modify the linked list
head = modifyContentsWrapper(head);
// Print the modified linked list
print(head);
</script>
Producción:
8 -> -2 -> 4 -> 12 -> 7 -> 10
Complejidad de tiempo : O (N), ya que estamos usando llamadas recursivas para atravesar N veces, donde N es el número de Nodes en la lista vinculada.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por Ashwin Loganathan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA