Dada una lista unida, con algunos números positivos (números válidos) y ceros (números no válidos). Convierta la lista enlazada de tal manera que si el próximo número válido es el mismo que el número actual, duplique su valor y reemplace el siguiente número con 0. Después de la modificación, reorganice la lista enlazada de modo que todos los 0 se desplacen al final.
Ejemplos:
Input : 2->2->0->4->0->8 Output : 4->4->8->0->0->0 Input : 0->2->2->2->0->6->6->0->0->8 Output : 4->2->12->8->0->0->0->0->0->0
Fuente: Experiencia de entrevista de IDC de Microsoft | Conjunto 156.
Enfoque: primero modifique la lista vinculada como se mencionó, es decir, si el siguiente número válido es el mismo que el número actual, duplique su valor y reemplace el siguiente número con 0.
Algoritmo de modificación:
1. ptr = head 2. while (ptr && ptr->next) 3. if (ptr->data == 0) || (ptr->data != ptr->next->data) 4. ptr = ptr->next 5. else 6. ptr->data = 2 * ptr->data 7. ptr->next->data = 0 8. ptr = ptr->next->next
Después de modificar la lista, separe los elementos válidos (distintos de cero) e inválidos (cero). Es lo mismo que segregar los Nodes pares e impares en una lista enlazada .
Implementación:
C++
// C++ implementation to modify and
// rearrange list
#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
int data;
Node* next;
};
// function to get a new node
Node* getNode(int data)
{
// allocate space
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// function to segregate valid (non-zero) numbers and
// invalid (zero) numbers in a list
Node* segValidInvalidNum(Node* head)
{
// valid (non-zero numbers) list start and
// end pointers
Node *validStart = NULL, *validEnd = NULL;
// invalid (zero numbers) list start and
// end pointers
Node *invalidStart = NULL, *invalidEnd = NULL;
Node* currentNode = head;
// traverse the given list
while (currentNode != NULL) {
// current node's data
int element = currentNode->data;
// if it is a non-zero element, then
// add it to valid list
if (element != 0) {
if (validStart == NULL) {
validStart = currentNode;
validEnd = validStart;
}
else {
validEnd->next = currentNode;
validEnd = validEnd->next;
}
}
// else it is a zero element, so
// add it to invalid list
else {
if (invalidStart == NULL) {
invalidStart = currentNode;
invalidEnd = invalidStart;
}
else {
invalidEnd->next = currentNode;
invalidEnd = invalidEnd->next;
}
}
// Move to the next node
currentNode = currentNode->next;
}
// if true then return the original list as it is
if (validStart == NULL || invalidStart == NULL)
return head;
// add the invalid list to the end of valid list
validEnd->next = invalidStart;
invalidEnd->next = NULL;
head = validStart;
// required head of the new list
return head;
}
// function to modify and
// rearrange list
Node* modifyAndRearrangeList(Node* head)
{
// if list is empty or contains a single
// element only
if (head == NULL || head->next == NULL)
return head;
// traverse the list
Node* ptr = head;
while (ptr && ptr->next) {
// if current node's data is '0' or it is not equal
// to next nodes data, them move one node ahead
if ((ptr->data == 0) || (ptr->data != ptr->next->data))
ptr = ptr->next;
else {
// double current node's data
ptr->data = 2 * ptr->data;
// put '0' in next node's data
ptr->next->data = 0;
// move two nodes ahead
ptr = ptr->next->next;
}
}
// segregate valid (non-zero) and
// invalid (non-zero) numbers
return segValidInvalidNum(head);
}
// function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
Node* head = getNode(2);
head->next = getNode(2);
head->next->next = getNode(0);
head->next->next->next = getNode(4);
head->next->next->next->next = getNode(0);
head->next->next->next->next->next = getNode(8);
cout << "Original List: ";
printList(head);
head = modifyAndRearrangeList(head);
cout << "\nModified List: ";
printList(head);
return 0;
}
Java
// Java implementation to modify and
// rearrange list
class GFG
{
// structure of a node
static class Node
{
int data;
Node next;
};
// function to get a new node
static Node getNode(int data)
{
// allocate space
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to segregate valid (non-zero) numbers
// and invalid (zero) numbers in a list
static Node segValidInvalidNum(Node head)
{
// valid (non-zero numbers) list start
// and end pointers
Node validStart = null, validEnd = null;
// invalid (zero numbers) list start and
// end pointers
Node invalidStart = null, invalidEnd = null;
Node currentNode = head;
// traverse the given list
while (currentNode != null)
{
// current node's data
int element = currentNode.data;
// if it is a non-zero element, then
// add it to valid list
if (element != 0)
{
if (validStart == null)
{
validStart = currentNode;
validEnd = validStart;
}
else
{
validEnd.next = currentNode;
validEnd = validEnd.next;
}
}
// else it is a zero element, so
// add it to invalid list
else
{
if (invalidStart == null)
{
invalidStart = currentNode;
invalidEnd = invalidStart;
}
else
{
invalidEnd.next = currentNode;
invalidEnd = invalidEnd.next;
}
}
// Move to the next node
currentNode = currentNode.next;
}
// if true then return the original list as it is
if (validStart == null || invalidStart == null)
return head;
// add the invalid list to the end of valid list
validEnd.next = invalidStart;
invalidEnd.next = null;
head = validStart;
// required head of the new list
return head;
}
// function to modify and
// rearrange list
static Node modifyAndRearrangeList(Node head)
{
// if list is empty or contains a single
// element only
if (head == null || head.next == null)
return head;
// traverse the list
Node ptr = head;
while (ptr != null && ptr.next != null)
{
// if current node's data is '0' or
// it is not equal to next nodes data,
// them move one node ahead
if ((ptr.data == 0) ||
(ptr.data != ptr.next.data))
ptr = ptr.next;
else
{
// double current node's data
ptr.data = 2 * ptr.data;
// put '0' in next node's data
ptr.next.data = 0;
// move two nodes ahead
ptr = ptr.next.next;
}
}
// segregate valid (non-zero) and
// invalid (non-zero) numbers
return segValidInvalidNum(head);
}
// function to print a linked list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver Code
public static void main(String[] args)
{
Node head = getNode(2);
head.next = getNode(2);
head.next.next = getNode(0);
head.next.next.next = getNode(4);
head.next.next.next.next = getNode(0);
head.next.next.next.next.next = getNode(8);
System.out.print("Original List: ");
printList(head);
head = modifyAndRearrangeList(head);
System.out.print("\nModified List: ");
printList(head);
}
}
// This code is contributed by Rajput-Ji
Python
# Python implementation to modify and
# rearrange list
# structure of a node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# function to get a new node
def getNode( data) :
# allocate space
newNode = Node(0)
# put in the data
newNode.data = data
newNode.next = None
return newNode
# function to segregate valid (non-zero) numbers
# and invalid (zero) numbers in a list
def segValidInvalidNum(head) :
# valid (non-zero numbers) list start
# and end pointers
validStart = None
validEnd = None
# invalid (zero numbers) list start and
# end pointers
invalidStart = None
invalidEnd = None
currentNode = head
# traverse the given list
while (currentNode != None) :
# current node's data
element = currentNode.data
# if it is a non-zero element, then
# add it to valid list
if (element != 0):
if (validStart == None):
validStart = currentNode
validEnd = validStart
else:
validEnd.next = currentNode
validEnd = validEnd.next
# else it is a zero element, so
# add it to invalid list
else:
if (invalidStart == None):
invalidStart = currentNode
invalidEnd = invalidStart
else:
invalidEnd.next = currentNode
invalidEnd = invalidEnd.next
# Move to the next node
currentNode = currentNode.next
# if true then return the original list as it is
if (validStart == None or invalidStart == None):
return head
# add the invalid list to the end of valid list
validEnd.next = invalidStart
invalidEnd.next = None
head = validStart
# required head of the new list
return head
# function to modify and
# rearrange list
def modifyAndRearrangeList( head) :
# if list is empty or contains a single
# element only
if (head == None or head.next == None):
return head
# traverse the list
ptr = head
while (ptr != None and ptr.next != None) :
# if current node's data is '0' or
# it is not equal to next nodes data,
# them move one node ahead
if ((ptr.data == 0) or
(ptr.data != ptr.next.data)) :
ptr = ptr.next
else:
# double current node's data
ptr.data = 2 * ptr.data
# put '0' in next node's data
ptr.next.data = 0
# move two nodes ahead
ptr = ptr.next.next
# segregate valid (non-zero) and
# invalid (non-zero) numbers
return segValidInvalidNum(head)
# function to print a linked list
def printList( head) :
while (head != None):
print(head.data, end = " ")
head = head.next
# Driver Code
head = getNode(2)
head.next = getNode(2)
head.next.next = getNode(0)
head.next.next.next = getNode(4)
head.next.next.next.next = getNode(0)
head.next.next.next.next.next = getNode(8)
print("Original List: ")
printList(head)
head = modifyAndRearrangeList(head)
print("\nModified List: ")
printList(head)
# This code is contributed by Arnab Kundu
C#
// C# implementation to modify and
// rearrange list
using System;
class GFG
{
// structure of a node
public class Node
{
public int data;
public Node next;
};
// function to get a new node
static Node getNode(int data)
{
// allocate space
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to segregate valid (non-zero) numbers
// and invalid (zero) numbers in a list
static Node segValidInvalidNum(Node head)
{
// valid (non-zero numbers) list
// start and end pointers
Node validStart = null,
validEnd = null;
// invalid (zero numbers) list start and
// end pointers
Node invalidStart = null,
invalidEnd = null;
Node currentNode = head;
// traverse the given list
while (currentNode != null)
{
// current node's data
int element = currentNode.data;
// if it is a non-zero element,
// then add it to valid list
if (element != 0)
{
if (validStart == null)
{
validStart = currentNode;
validEnd = validStart;
}
else
{
validEnd.next = currentNode;
validEnd = validEnd.next;
}
}
// else it is a zero element,
// so add it to invalid list
else
{
if (invalidStart == null)
{
invalidStart = currentNode;
invalidEnd = invalidStart;
}
else
{
invalidEnd.next = currentNode;
invalidEnd = invalidEnd.next;
}
}
// Move to the next node
currentNode = currentNode.next;
}
// if true then return the
// original list as it is
if (validStart == null ||
invalidStart == null)
return head;
// add the invalid list to
// the end of valid list
validEnd.next = invalidStart;
invalidEnd.next = null;
head = validStart;
// required head of the new list
return head;
}
// function to modify and
// rearrange list
static Node modifyAndRearrangeList(Node head)
{
// if list is empty or contains
// a single element only
if (head == null ||
head.next == null)
return head;
// traverse the list
Node ptr = head;
while (ptr != null &&
ptr.next != null)
{
// if current node's data is '0' or
// it is not equal to next nodes data,
// them move one node ahead
if ((ptr.data == 0) ||
(ptr.data != ptr.next.data))
ptr = ptr.next;
else
{
// double current node's data
ptr.data = 2 * ptr.data;
// put '0' in next node's data
ptr.next.data = 0;
// move two nodes ahead
ptr = ptr.next.next;
}
}
// segregate valid (non-zero) and
// invalid (non-zero) numbers
return segValidInvalidNum(head);
}
// function to print a linked list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
}
// Driver Code
public static void Main(String[] args)
{
Node head = getNode(2);
head.next = getNode(2);
head.next.next = getNode(0);
head.next.next.next = getNode(4);
head.next.next.next.next = getNode(0);
head.next.next.next.next.next = getNode(8);
Console.Write("Original List: ");
printList(head);
head = modifyAndRearrangeList(head);
Console.Write("\nModified List: ");
printList(head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation to modify and
// rearrange list
// structure of a node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// function to get a new node
function getNode(data) {
// allocate space
var newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to segregate valid (non-zero) numbers
// and invalid (zero) numbers in a list
function segValidInvalidNum(head) {
// valid (non-zero numbers) list
// start and end pointers
var validStart = null,
validEnd = null;
// invalid (zero numbers) list start and
// end pointers
var invalidStart = null,
invalidEnd = null;
var currentNode = head;
// traverse the given list
while (currentNode != null) {
// current node's data
var element = currentNode.data;
// if it is a non-zero element,
// then add it to valid list
if (element != 0) {
if (validStart == null) {
validStart = currentNode;
validEnd = validStart;
} else {
validEnd.next = currentNode;
validEnd = validEnd.next;
}
}
// else it is a zero element,
// so add it to invalid list
else {
if (invalidStart == null) {
invalidStart = currentNode;
invalidEnd = invalidStart;
} else {
invalidEnd.next = currentNode;
invalidEnd = invalidEnd.next;
}
}
// Move to the next node
currentNode = currentNode.next;
}
// if true then return the
// original list as it is
if (validStart == null || invalidStart == null) return head;
// add the invalid list to
// the end of valid list
validEnd.next = invalidStart;
invalidEnd.next = null;
head = validStart;
// required head of the new list
return head;
}
// function to modify and
// rearrange list
function modifyAndRearrangeList(head) {
// if list is empty or contains
// a single element only
if (head == null || head.next == null) return head;
// traverse the list
var ptr = head;
while (ptr != null && ptr.next != null) {
// if current node's data is '0' or
// it is not equal to next nodes data,
// them move one node ahead
if (ptr.data == 0 || ptr.data != ptr.next.data) ptr = ptr.next;
else {
// double current node's data
ptr.data = 2 * ptr.data;
// put '0' in next node's data
ptr.next.data = 0;
// move two nodes ahead
ptr = ptr.next.next;
}
}
// segregate valid (non-zero) and
// invalid (non-zero) numbers
return segValidInvalidNum(head);
}
// function to print a linked list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver Code
var head = getNode(2);
head.next = getNode(2);
head.next.next = getNode(0);
head.next.next.next = getNode(4);
head.next.next.next.next = getNode(0);
head.next.next.next.next.next = getNode(8);
document.write("Original List: ");
printList(head);
head = modifyAndRearrangeList(head);
document.write("<br>Modified List: ");
printList(head);
// This code is contributed by rdtank.
</script>
Producción
Original List: 2 2 0 4 0 8 Modified List: 4 4 8 0 0 0
Complejidad temporal: O(n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA