Dada una lista enlazada con unos dos Nodes repetidos adyacentes antes de un cero, la tarea es duplicar el primero y hacer el siguiente 0. Después de esto, agregue todos los ceros a la cola.
Requisito previo: Conceptos básicos de la implementación de la lista enlazada individual
Ejemplos:
Input : 4 -> 4 -> 0 -> 2 -> 3 -> 4 ->
3 -> 3 -> 0 -> 4 ->
Output : 8-> 2-> 3-> 4-> 6-> 4-> 0->
0-> 0-> 0->
Explanation :
First, after doubling the first element and making
second element 0 before all zeros.
8 -> 0 -> 0 -> 2 -> 3 -> 4 -> 6 -> 0
-> 0 -> 4 ->
Next :
8 -> 6 -> 5 -> 6 -> 0 -> 0 -> 0 ->
0 -> 0 -> 0 -> 0 ->
Input : 0 -> 4 -> 4 -> 0 -> 3 -> 3 -> 0
-> 5 -> 0 -> 0 -> 6 ->
Output : 8 -> 6 -> 5 -> 6 -> 0 -> 0 -> 0
-> 0 -> 0 -> 0 -> 0 ->
Recorra la lista enlazada, y donde haya dos mismos datos adyacentes de Nodes antes de un 0 (por ejemplo, 4 -> 4 -> 0), luego, doble el primer elemento y haga otro como 0 (por ejemplo, 8 -> 0 -> 0 – >). Finalmente, recorra la lista enlazada y apunte linealmente todos los ceros a la cola.
Java
// Java code to modify linked list
import java.util.*;
// Linked List Node
class Node {
int data;
Node next;
// Constructor
public Node(int data)
{
this.data = data;
next = null;
}
}
// Class to perform operations
// on linked list
class GfG {
// Recursive function to double the one of two
// elements and make next one as 0,
// which are equal before 0
public static void changeTwoBefore0(Node head)
{
// there should be atleast three elements
// to perform required operation
if (head == null || head.next == null
|| head.next.next == null)
return;
// when two continuous elements
// are same
if ((head.data == head.next.data)
&& (head.next.next.data == 0)) {
int temp = head.data;
head.data = 2 * temp;
head.next.data = 0;
if (head.next.next.next != null)
head = head.next.next.next;
else
return;
}
else
head = head.next;
// recursive call to changeTwoBefore0
// for next element
changeTwoBefore0(head);
}
// function to append zeros at tail
public static Node appendZero(Node head)
{
if (head == null || head.next == null)
return head;
// Find tail node
Node tail = head;
while (tail.next != null)
tail = tail.next;
Node origTail = tail;
// Case when starting nodes have 0 values
// we need to change head in this case.
Node curr = head;
while (curr.next != null && curr.data == 0) {
tail.next = curr;
tail = curr;
curr = curr.next;
}
head = curr;
// Now moving other 0s to end
Node prev = curr;
curr = curr.next;
// We check until original tail
while (curr != origTail) {
// If current data is 0, append
// after tail and update tail.
if (curr.data == 0) {
tail.next = curr;
tail = curr;
prev.next = curr.next;
}
else
prev = curr;
// We always move current
curr = curr.next;
}
// Finally making sure that linked
// list is null terminated.
tail.next = null;
return head;
}
public static Node doubleAndAppend0(Node head)
{
// Change two same nodes before 0
changeTwoBefore0(head);
// Move all 0s to end
return appendZero(head);
}
// function to display the nodes
public static void display(Node head)
{
while (head != null) {
System.out.print(head.data + " -> ");
head = head.next;
}
}
// Driver code
public static void main(String[] args)
{
Node head = new Node(4);
head.next = new Node(4);
head.next.next = new Node(0);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(3);
head.next.next.next.next.next = new Node(4);
head.next.next.next.next.next.next = new Node(3);
head.next.next.next.next.next.next.next
= new Node(3);
head.next.next.next.next.next.next.next.next
= new Node(0);
head.next.next.next.next.next.next.next.next.next
= new Node(4);
System.out.println("Original linked list :");
display(head);
head = doubleAndAppend0(head);
System.out.println("\nModified linked list :");
display(head);
}
}
C++
// C++ code to modify linked list
#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {
public:
int data;
Node* next;
// Constructor
public:
Node(int dat)
{
data = dat;
next = NULL;
}
};
// Recursive function to double the one of two
// elements and make next one as 0,
// which are equal before 0
void changeTwoBefore0(Node* head)
{
// there should be atleast three elements
// to perform required operation
if (head == NULL || head->next == NULL
|| head->next->next == NULL)
return;
// when two continuous elements
// are same
if ((head->data == head->next->data)
&& (head->next->next->data == 0))
{
int temp = head->data;
head->data = 2 * temp;
head->next->data = 0;
if (head->next->next->next != NULL)
head = head->next->next->next;
else
return;
}
else
head = head->next;
// recursive call to changeTwoBefore0
// for next element
changeTwoBefore0(head);
}
// function to append zeros at tail
Node* appendZero(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
// Find tail node
Node* tail = head;
while (tail->next != NULL)
tail = tail->next;
Node* origTail = tail;
// Case when starting nodes have 0 values
// we need to change head in this case.
Node* curr = head;
while (curr->next != NULL && curr->data == 0)
{
tail->next = curr;
tail = curr;
curr = curr->next;
}
head = curr;
// Now moving other 0s to end
Node* prev = curr;
curr = curr->next;
// We check until original tail
while (curr != origTail)
{
// If current data is 0, append
// after tail and update tail.
if (curr->data == 0)
{
tail->next = curr;
tail = curr;
prev->next = curr->next;
}
else
prev = curr;
// We always move current
curr = curr->next;
}
// Finally making sure that linked
// list is NULL terminated.
tail->next = NULL;
return head;
}
Node* doubleAndAppend0(Node* head)
{
// Change two same nodes before 0
changeTwoBefore0(head);
// Move all 0s to end
return appendZero(head);
}
// function to display the nodes
void display(Node* head)
{
while (head != NULL) {
cout << head->data << " -> ";
head = head->next;
}
}
// Driver Code
int main()
{
Node* head = new Node(4);
head->next = new Node(4);
head->next->next = new Node(0);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(3);
head->next->next->next->next->next = new Node(4);
head->next->next->next->next->next->next = new Node(3);
head->next->next->next->next->next->next->next
= new Node(3);
head->next->next->next->next->next->next->next->next
= new Node(0);
head->next->next->next->next->next->next->next->next
->next
= new Node(4);
cout << "Original linked list :";
display(head);
head = doubleAndAppend0(head);
cout << "\nModified linked list :";
display(head);
return 0;
}
// contributed by ajaykr00kj
Python3
# Python3 code to modify linked list
# Linked List Node
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
# Recursive function to double the one of two
# elements and make next one as 0,
# which are equal before 0
def changeTwoBefore0 (head):
# there should be atleast three elements
# to perform required operation
if (head == None or head.next == None or head.next.next == None):
return
# when two continuous elements
# are same
if ((head.data == head.next.data) and (head.next.next.data == 0)):
temp = head.data
head.data = 2*temp
head.next.data = 0
if (head.next.next.next != None):
head = head.next.next.next
else:
return
else:
head = head.next
# recursive call to changeTwoBefore0
# for next element
changeTwoBefore0(head)
# function to append zeros at tail
def appendZero( head):
if (head == None or head.next == None):
return head
# Find tail node
tail = head
while (tail.next != None):
tail = tail.next
origTail = tail
# Case when starting nodes have 0 values
# we need to change head in this case.
curr = head
while (curr.next != None and curr.data == 0):
tail.next = curr
tail = curr
curr = curr.next
head = curr
# Now moving other 0s to end
prev = curr
curr = curr.next
# We check until original tail
while (curr != origTail):
# If current data is 0, append
# after tail and update tail.
if (curr.data == 0):
tail.next = curr
tail = curr
prev.next = curr.next
else:
prev = curr
# We always move current
curr = curr.next
# Finally making sure that linked
# list is None terminated.
tail.next = None
return head
def doubleAndAppend0(head):
# Change two same nodes before 0
changeTwoBefore0(head)
# Move all 0s to end
return appendZero(head)
# function to display the nodes
def display( head):
while (head != None):
print(head.data ,end = " -> ")
head = head.next
# Driver code
head = Node(4)
head.next = Node(4)
head.next.next = Node(0)
head.next.next.next = Node(2)
head.next.next.next.next = Node(3)
head.next.next.next.next.next = Node(4)
head.next.next.next.next.next.next = Node(3)
head.next.next.next.next.next.next.next = Node(3)
head.next.next.next.next.next.next.next.next = Node(0)
head.next.next.next.next.next.next.next.next.next = Node(4)
print("Original linked list :")
display(head)
head = doubleAndAppend0(head)
print("\nModified linked list :")
display(head)
# This code is contributed by Arnab Kundu
C#
// C# code to modify linked list
using System;
// Linked List Node
public class Node
{
public int data;
public Node next;
// Constructor
public Node(int data)
{
this.data = data;
next = null;
}
}
// Class to perform operations
// on linked list
public class GfG
{
// Recursive function to double the one of two
// elements and make next one as 0,
// which are equal before 0
public static void changeTwoBefore0(Node head)
{
// there should be atleast three elements
// to perform required operation
if (head == null || head.next == null ||
head.next.next == null)
return;
// when two continuous elements
// are same
if ((head.data == head.next.data) &&
(head.next.next.data == 0))
{
int temp = head.data;
head.data = 2*temp;
head.next.data = 0;
if (head.next.next.next != null)
head = head.next.next.next;
else
return;
}
else
head = head.next;
// recursive call to changeTwoBefore0
// for next element
changeTwoBefore0(head);
}
// function to append zeros at tail
public static Node appendZero(Node head)
{
if (head == null || head.next == null)
return head;
// Find tail node
Node tail = head;
while (tail.next != null)
tail = tail.next;
Node origTail = tail;
// Case when starting nodes have 0 values
// we need to change head in this case.
Node curr = head;
while (curr.next != null && curr.data == 0)
{
tail.next = curr;
tail = curr;
curr = curr.next;
}
head = curr;
// Now moving other 0s to end
Node prev = curr;
curr = curr.next;
// We check until original tail
while (curr != origTail)
{
// If current data is 0, append
// after tail and update tail.
if (curr.data == 0)
{
tail.next = curr;
tail = curr;
prev.next = curr.next;
}
else
prev = curr;
// We always move current
curr = curr.next;
}
// Finally making sure that linked
// list is null terminated.
tail.next = null;
return head;
}
public static Node doubleAndAppend0(Node head)
{
// Change two same nodes before 0
changeTwoBefore0(head);
// Move all 0s to end
return appendZero(head);
}
// function to display the nodes
public static void display(Node head)
{
while (head != null)
{
Console.Write(head.data + " -> ");
head = head.next;
}
}
// Driver code
public static void Main()
{
Node head = new Node(4);
head.next = new Node(4);
head.next.next = new Node(0);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(3);
head.next.next.next.next.next = new Node(4);
head.next.next.next.next.next.next = new Node(3);
head.next.next.next.next.next.next.next = new Node(3);
head.next.next.next.next.next.next.next.next = new Node(0);
head.next.next.next.next.next.next.next.next.next = new Node(4);
Console.Write("Original linked list :\n");
display(head);
head = doubleAndAppend0(head);
Console.WriteLine("\nModified linked list :");
display(head);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript code to modify linked list
// Linked List Node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// Class to perform operations
// on linked list
// Recursive function to double the one of two
// elements and make next one as 0,
// which are equal before 0
function changeTwoBefore0(head)
{
// there should be atleast three elements
// to perform required operation
if (head == null || head.next == null ||
head.next.next == null)
return;
// when two continuous elements
// are same
if ((head.data == head.next.data) &&
(head.next.next.data == 0))
{
var temp = head.data;
head.data = 2*temp;
head.next.data = 0;
if (head.next.next.next != null)
head = head.next.next.next;
else
return;
}
else
head = head.next;
// recursive call to changeTwoBefore0
// for next element
changeTwoBefore0(head);
}
// function to append zeros at tail
function appendZero(head)
{
if (head == null || head.next == null)
return head;
// Find tail node
var tail = head;
while (tail.next != null)
tail = tail.next;
var origTail = tail;
// Case when starting nodes have 0 values
// we need to change head in this case.
var curr = head;
while (curr.next != null && curr.data == 0)
{
tail.next = curr;
tail = curr;
curr = curr.next;
}
head = curr;
// Now moving other 0s to end
var prev = curr;
curr = curr.next;
// We check until original tail
while (curr != origTail)
{
// If current data is 0, append
// after tail and update tail.
if (curr.data == 0)
{
tail.next = curr;
tail = curr;
prev.next = curr.next;
}
else
prev = curr;
// We always move current
curr = curr.next;
}
// Finally making sure that linked
// list is null terminated.
tail.next = null;
return head;
}
function doubleAndAppend0(head)
{
// Change two same nodes before 0
changeTwoBefore0(head);
// Move all 0s to end
return appendZero(head);
}
// function to display the nodes
function display( head)
{
while (head != null)
{
document.write(head.data + " -> ");
head = head.next;
}
}
// Driver code
var head = new Node(4);
head.next = new Node(4);
head.next.next = new Node(0);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(3);
head.next.next.next.next.next = new Node(4);
head.next.next.next.next.next.next = new Node(3);
head.next.next.next.next.next.next.next = new Node(3);
head.next.next.next.next.next.next.next.next = new Node(0);
head.next.next.next.next.next.next.next.next.next = new Node(4);
document.write("Original linked list :<br>");
display(head);
head = doubleAndAppend0(head);
document.write("<br>Modified linked list :<br>");
display(head);
</script>
Producción
Original linked list : 4 -> 4 -> 0 -> 2 -> 3 -> 4 -> 3 -> 3 -> 0 -> 4 -> Modified linked list : 8 -> 2 -> 3 -> 4 -> 6 -> 4 -> 0 -> 0 -> 0 -> 0 ->
Complejidad temporal: O(n), donde n es el número de Nodes de la lista enlazada.
Publicación traducida automáticamente
Artículo escrito por Dhiman Mayank y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA