Dada una lista enlazada codificada que se codifica utilizando el algoritmo de codificación de longitud de ejecución . La tarea es decodificar la lista enlazada dada y generar la string de entrada.
Codificación de longitud de ejecución: en la codificación de longitud de ejecución, la string de entrada se codifica reemplazando una substring de caracteres repetidos en la string por el carácter seguido de su recuento. Si el carácter es único y no se repite, su recuento no se suma. Por ejemplo, si la string de entrada es «wwwwaaadexxxxxx», la función debería devolver «w4a3dex6»
. Ejemplos:
Entrada: Lista = a->5->b->r->3->NULL
Salida: string = “aaaaabrrr”
Explicación:
De la lista enlazada, el carácter es ‘a’ y su cuenta es 5 , por lo que el carácter se repite 5 veces
El siguiente carácter es ‘b’ y el siguiente carácter no es un número, por lo tanto, el carácter ‘b’ se repite solo una vez.
El siguiente carácter es ‘r’ y la cuenta es 3 , por lo que el carácter se repite 3 veces .
Entrada: Lista = a->b->r->3->a->3->NULL
Salida: string = “abrrraaa”
Enfoque :
- Recorra la lista enlazada.
- Almacene el carácter actual en una variable c .
- Verifique si el siguiente Node es un número y almacene el número en el conteo , de lo contrario, el conteo es 1 .
- Agregue el carácter c a la lista de tiempos de conteo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to decode a linked list
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node {
char data;
struct Node* next;
};
// Utility function to create a new Node
Node* newNode(char data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to append nodes to a list
void append(struct Node* head_ref, char new_data)
{
struct Node* new_node = new Node;
struct Node* last = head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (head_ref == NULL) {
head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
// Function to print list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Function to decode the linked list
string decodeList(Node* head)
{
Node* p = head;
string res = "";
int count;
// While there are nodes left
while (p) {
// To store the count by which the current
// character needs to be repeated
count = 0;
// Get the current character
char c = p->data;
if (p->next) {
Node* temp = p->next;
// If current node is a digit
if (temp && temp->data >= '0'
&& temp->data <= '9') {
// Generate the integer from
// the consecutive digits
while (temp && temp->data >= '0'
&& temp->data <= '9') {
count = count * 10 + (temp->data - '0');
temp = temp->next;
}
p = temp;
}
else {
count = 1;
p = p->next;
}
}
else {
count = 1;
p = p->next;
}
// Repeat the character count times
for (int i = 0; i < count; i++) {
res += c;
}
}
return res;
}
// Driver code
int main()
{
// Creating the linked list
Node* head = newNode('a');
head->next = newNode('5');
head->next->next = newNode('b');
head->next->next->next = newNode('r');
cout << decodeList(head);
return 0;
}
Java
// Java program to decode a linked list
class GFG {
// Linked list node
static class Node {
char data;
Node next;
};
// Utility function to create a new Node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to append nodes to a list
static void append(Node head_ref, char new_data)
{
Node new_node = new Node();
Node last = head_ref;
new_node.data = new_data;
new_node.next = null;
if (head_ref == null) {
head_ref = new_node;
return;
}
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
// Function to print list
static void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Function to decode the linked list
static String decodeList(Node head)
{
// Pointer used to traverse through all
// the nodes in the list
Node p = head;
// String to store the decoded message
String res = "";
int count;
// While there are nodes left
while (p != null) {
// To store the count by which the current
// character needs to be repeated
count = 0;
// Get the current character
char c = p.data;
if (p.next != null) {
Node temp = p.next;
// If current node is a digit
if (temp != null && temp.data >= '0'
&& temp.data <= '9') {
// Generate the integer from
// the consecutive digits
while (temp != null && temp.data >= '0'
&& temp.data <= '9') {
count = count * 10 + (temp.data - '0');
temp = temp.next;
}
p = temp;
}
else {
count = 1;
p = p.next;
}
}
else {
count = 1;
p = p.next;
}
// Repeat the character count times
for (int i = 0; i < count; i++) {
res += c;
}
}
return res;
}
// Driver code
public static void main(String args[])
{
// Creating the linked list
Node head = newNode('a');
head.next = newNode('5');
head.next.next = newNode('b');
head.next.next.next = newNode('r');
System.out.println(decodeList(head));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to decode a linked list
# Linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Utility function to create a Node
def newNode(data):
temp = Node(data);
temp.next = None;
return temp;
# Function to append nodes to a list
def append(head_ref, new_data):
new_node = Node;
last = head_ref;
new_node.data = new_data;
new_node.next = None;
if (head_ref == None):
head_ref = new_node;
return;
while (last.next != None):
last = last.next;
last.next = new_node;
return;
# Function to print list
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next;
# Function to decode the linked list
def decodeList(head):
p = head;
res = "";
count = 0
# While there are nodes left
while (p != None):
# To store the count by which the current
# character needs to be repeated
count = 0;
# Get the current character
c = p.data;
if (p.next != None):
temp = p.next;
# If current node is a digit
if (temp != None and ord(temp.data) >= ord('0')
and ord(temp.data) <= ord('9')):
# Generate the integer from
# the consecutive digits
while (temp != None and ord(temp.data) >= ord('0')
and ord(temp.data) <= ord('9')):
count = count * 10 + ord(temp.data) - ord('0')
temp = temp.next;
p = temp;
else:
count = 1;
p = p.next;
else:
count = 1;
p = p.next;
# Repeat the character count times
for i in range(0, count):
res += c;
return res;
# Driver code
if __name__=='__main__':
# Creating the linked list
head = newNode('a');
head.next = newNode('5');
head.next.next = newNode('b');
head.next.next.next = newNode('r');
print(decodeList(head))
# This code is contributed by rutvik_56
C#
// C# program to decode a linked list
using System;
public class GFG {
// Linked list node
public class Node {
public char data;
public Node next;
};
// Utility function to create a new Node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to append nodes to a list
static void append(Node head_ref, char new_data)
{
Node new_node = new Node();
Node last = head_ref;
new_node.data = new_data;
new_node.next = null;
if (head_ref == null) {
head_ref = new_node;
return;
}
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
// Function to print list
static void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Function to decode the linked list
static String decodeList(Node head)
{
// Pointer used to traverse through all
// the nodes in the list
Node p = head;
// String to store the decoded message
String res = "";
int count;
// While there are nodes left
while (p != null) {
// To store the count by which the current
// character needs to be repeated
count = 0;
// Get the current character
char c = p.data;
if (p.next != null) {
Node temp = p.next;
// If current node is a digit
if (temp != null && temp.data >= '0'
&& temp.data <= '9') {
// Generate the integer from
// the consecutive digits
while (temp != null && temp.data >= '0'
&& temp.data <= '9') {
count = count * 10 + (temp.data - '0');
temp = temp.next;
}
p = temp;
}
else {
count = 1;
p = p.next;
}
}
else {
count = 1;
p = p.next;
}
// Repeat the character count times
for (int i = 0; i < count; i++) {
res += c;
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
// Creating the linked list
Node head = newNode('a');
head.next = newNode('5');
head.next.next = newNode('b');
head.next.next.next = newNode('r');
Console.WriteLine(decodeList(head));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to decode a linked list
// Linked list node
class Node {
constructor() {
this.data = 0;
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 append nodes to a list
function append(head_ref, new_data) {
var new_node = new Node();
var last = head_ref;
new_node.data = new_data;
new_node.next = null;
if (head_ref == null) {
head_ref = new_node;
return;
}
while (last.next != null) last = last.next;
last.next = new_node;
return;
}
// Function to print list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Function to decode the linked list
function decodeList(head) {
// Pointer used to traverse through all
// the nodes in the list
var p = head;
// String to store the decoded message
var res = "";
var count;
// While there are nodes left
while (p != null) {
// To store the count by which the current
// character needs to be repeated
count = 0;
// Get the current character
var c = p.data;
if (p.next != null) {
var temp = p.next;
// If current node is a digit
if (temp != null && temp.data >= "0" &&
temp.data <= "9") {
// Generate the integer from
// the consecutive digits
while (temp != null && temp.data >= "0" &&
temp.data <= "9") {
count = count * 10 + (temp.data - "0");
temp = temp.next;
}
p = temp;
} else {
count = 1;
p = p.next;
}
} else {
count = 1;
p = p.next;
}
// Repeat the character count times
for (var i = 0; i < count; i++) {
res += c;
}
}
return res;
}
// Driver code
// Creating the linked list
var head = newNode("a");
head.next = newNode("5");
head.next.next = newNode("b");
head.next.next.next = newNode("r");
document.write(decodeList(head));
</script>
Producción:
aaaaabr