Dada una lista enlazada. La tarea es cambiar el valor del Node anterior y siguiente de un Node a 0 si el Node actual es 0.
Ejemplos:
Input : 2->3->4->5->0->9->0->9->NULL Output : 2->3->4->0->0->0->0->0->NULL Input : 0->2->3->4->0->0->NULL Output : 0->0->3->0->0->0->NULL
Algoritmo :
- El primer paso es crear dos punteros prev y curr . Prev apuntará al
Node anterior y curr al Node actual . La razón para hacer uso de prev es que no podemos retroceder en una lista enlazada individualmente. - si el primer Node es 0 , compruebe si el siguiente Node es 0
- Si es así , salte
- de lo contrario, cambie el siguiente Node a -1 .
- Comience a iterar a través de los Nodes de la lista.
- si el Node actual es 0 y la variable temp es 0 entonces
- establezca el Node anterior en -1 .
- establezca la variable temporal en 1 .
- si el valor temporal es 1 y los datos del Node actual no son 1 , establezca el Node actual en -1
- si el Node actual es 0 y la variable temp es 0 entonces
- Repita el paso 3 hasta llegar al final de la lista.
- Recorra la lista y cambie los Nodes con valor -1 a 0 .
La razón para hacer uso de temp y -1 es que si cambiamos el siguiente Node a 0 directamente, esto puede conducir a cambiar el Node siguiente a 0 como resultado de lo cual la lista completa puede cambiar a 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to update the adjacent
// nodes in a linked list
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
};
// Utility function to create a new Node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to display the linked list
void printList(Node* node)
{
// iterate until end of the list is reached
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Function to update the adjacent
// nodes to zero
void updateAdjacent(Node* head)
{
// Pointer to point to
// the previous node
Node* prev = head;
// Pointer to the
// current node
Node* curr = head->next;
// If the first node is zero and the
// second node is not zero then change
// the value to -1
if (prev->data == 0 && curr->data != 0)
curr->data = -1;
// Temp variable to denote if the
// current node is zero then the next
// node will be changed to zero
int temp = 0;
while (curr != NULL) {
// if the temp variable is 1 and
// current data is not zero
if (temp == 1 && curr->data != 0) {
// change the data to -1
curr->data = -1;
temp = 0;
}
// if the data is zero
if (curr->data == 0) {
// set the temp variable to 1
temp = 1;
// set the previous node data to -1
prev->data = -1;
}
curr = curr->next;
prev = prev->next;
}
curr = head;
// change all the nodes with -1 to 0
while (curr != NULL) {
if (curr->data == -1)
curr->data = 0;
curr = curr->next;
}
}
// Driver code
int main()
{
// creating the linked list
Node* head = newNode(2);
head->next = newNode(3);
head->next->next = newNode(4);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(0);
head->next->next->next->next->next = newNode(9);
head->next->next->next->next->next->next = newNode(0);
head->next->next->next->next->next->next->next = newNode(9);
updateAdjacent(head);
printList(head);
return 0;
}
Java
// Java program to update the adjacent
// nodes in a linked list
class GFG
{
// A linked list node
static class Node
{
int data;
Node next;
}
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to display the linked list
static void printList(Node node)
{
// iterate until end of the list is reached
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
// Function to update the adjacent
// nodes to zero
static void updateAdjacent(Node head)
{
// Pointer to point to
// the previous node
Node prev = head;
// Pointer to the
// current node
Node curr = head.next;
// If the first node is zero and the
// second node is not zero then change
// the value to -1
if (prev.data == 0 && curr.data != 0)
curr.data = -1;
// Temp variable to denote if the
// current node is zero then the next
// node will be changed to zero
int temp = 0;
while (curr != null)
{
// if the temp variable is 1 and
// current data is not zero
if (temp == 1 && curr.data != 0)
{
// change the data to -1
curr.data = -1;
temp = 0;
}
// if the data is zero
if (curr.data == 0)
{
// set the temp variable to 1
temp = 1;
// set the previous node data to -1
prev.data = -1;
}
curr = curr.next;
prev = prev.next;
}
curr = head;
// change all the nodes with -1 to 0
while (curr != null)
{
if (curr.data == -1)
curr.data = 0;
curr = curr.next;
}
}
// Driver code
public static void main(String[] args)
{
// creating the linked list
Node head = newNode(2);
head.next = newNode(3);
head.next.next = newNode(4);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(0);
head.next.next.next.next.next = newNode(9);
head.next.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next.next = newNode(9);
updateAdjacent(head);
printList(head);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to update the adjacent # nodes in a linked list # A linked list node class Node: def __init__(self, data): self.data = data self.next = None # Function to display the linked list def printList(node): # iterate until end of the # list is reached while node != None: print(node.data, end = " ") node = node.next # Function to update the adjacent # nodes to zero def updateAdjacent(head): # Pointer to point to # the previous node prev = head # Pointer to the # current node curr = head.next # If the first node is zero and the # second node is not zero then change # the value to -1 if prev.data == 0 and curr.data != 0: curr.data = -1 # Temp variable to denote if the # current node is zero then the next # node will be changed to zero temp = 0 while curr != None: # if the temp variable is 1 and # current data is not zero if temp == 1 and curr.data != 0: # change the data to -1 curr.data = -1 temp = 0 # if the data is zero if curr.data == 0: # set the temp variable to 1 temp = 1 # set the previous node data to -1 prev.data = -1 curr = curr.next prev = prev.next curr = head # change all the nodes with -1 to 0 while curr != None: if curr.data == -1: curr.data = 0 curr = curr.next # Driver Code if __name__ == "__main__": # creating the linked list head = Node(2) head.next = Node(3) head.next.next = Node(4) head.next.next.next = Node(5) head.next.next.next.next = Node(0) head.next.next.next.next.next = Node(9) head.next.next.next.next.next.next = Node(0) head.next.next.next.next.next.next.next = Node(9) updateAdjacent(head) printList(head) # This code is contributed by Rituraj Jain
C#
// C# program to update the adjacent
// nodes in a linked list
using System;
class GFG
{
// A linked list node
public class Node
{
public int data;
public Node next;
}
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to display the linked list
static void printList(Node node)
{
// iterate until end of the list is reached
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
// Function to update the adjacent
// nodes to zero
static void updateAdjacent(Node head)
{
// Pointer to point to
// the previous node
Node prev = head;
// Pointer to the
// current node
Node curr = head.next;
// If the first node is zero and the
// second node is not zero then change
// the value to -1
if (prev.data == 0 && curr.data != 0)
curr.data = -1;
// Temp variable to denote if the
// current node is zero then the next
// node will be changed to zero
int temp = 0;
while (curr != null)
{
// if the temp variable is 1 and
// current data is not zero
if (temp == 1 && curr.data != 0)
{
// change the data to -1
curr.data = -1;
temp = 0;
}
// if the data is zero
if (curr.data == 0)
{
// set the temp variable to 1
temp = 1;
// set the previous node data to -1
prev.data = -1;
}
curr = curr.next;
prev = prev.next;
}
curr = head;
// change all the nodes with -1 to 0
while (curr != null)
{
if (curr.data == -1)
curr.data = 0;
curr = curr.next;
}
}
// Driver code
public static void Main(String[] args)
{
// creating the linked list
Node head = newNode(2);
head.next = newNode(3);
head.next.next = newNode(4);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(0);
head.next.next.next.next.next = newNode(9);
head.next.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next.next = newNode(9);
updateAdjacent(head);
printList(head);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// javascript program to update the adjacent
// nodes in a linked list // A linked list node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Utility function to create a new Node
function newNode(data) {
var temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to display the linked list
function printList(node) {
// iterate until end of the list is reached
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Function to update the adjacent
// nodes to zero
function updateAdjacent(head) {
// Pointer to point to
// the previous node
var prev = head;
// Pointer to the
// current node
var curr = head.next;
// If the first node is zero and the
// second node is not zero then change
// the value to -1
if (prev.data == 0 && curr.data != 0)
curr.data = -1;
// Temp variable to denote if the
// current node is zero then the next
// node will be changed to zero
var temp = 0;
while (curr != null) {
// if the temp variable is 1 and
// current data is not zero
if (temp == 1 && curr.data != 0) {
// change the data to -1
curr.data = -1;
temp = 0;
}
// if the data is zero
if (curr.data == 0) {
// set the temp variable to 1
temp = 1;
// set the previous node data to -1
prev.data = -1;
}
curr = curr.next;
prev = prev.next;
}
curr = head;
// change all the nodes with -1 to 0
while (curr != null) {
if (curr.data == -1)
curr.data = 0;
curr = curr.next;
}
}
// Driver code
// creating the linked list
var head = newNode(2);
head.next = newNode(3);
head.next.next = newNode(4);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(0);
head.next.next.next.next.next = newNode(9);
head.next.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next.next = newNode(9);
updateAdjacent(head);
printList(head);
// This code is contributed by todaysgaurav
</script>
Producción:
2 3 4 0 0 0 0 0