# Run Length Decoding in Linked List

### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

We will be provided with a Linked List in encoded form (like a4de4f2) and we need to decode the given linked list and output the decoded version in the form of string.

##### Example ### Problem Statement Understanding

Giving you a brief description about run length encoding.

In Run Length Encoding, the input string is encoded by replacing a substring of a repeated character in the string by the character followed by its count. If the character is single and non-repeating, then it's count is not added.

For example

• If the input string is aaaa then its run length encoding will be a4
• If we add dd to the above string aaaa then the resultant string will be aaaadd and now its run length encoding will become a4d2.
• Similarly, if we add eee to the string aaaadd then the resultant string will be aaaaddeee and now its run length encoding will become a4d2e3.
• But there is case like if we add a single character to the like f to the string aaaaddeee, then the resultant string will be aaaaddeeef and its run length encoding will be a4d2e3f.

I think from the above pattern you got it how we are encoding the input string.

#### Example of Run Length Encoding

Output String (Encoded Using Run Length Algorithm) - a4de4f2

Now, since you have understood what Run length encoding is, let us move to our problem statement description.

We will be provided with a Linked List in encoded form (like a4de4f2) and we need to decode the given linked list and output the decoded version in the form of a string.

#### Considering same example for run length decoding Explanation : Given a linked list a → 4 → d → e → 4 → f → 2, which means that:

• a occur 4 times.
• d occur only once because following d there is no count i.e. the next node does not contain any digit representing the count of d.
• e occurs 4 times.
• f occurs 2 times.

Therefore, in output you need to print a string containing 4 times a, 1 time d , 4 times e and 2 times f, i.e., "aaaadeeeeff", which is our output.

### Approach and Algorithm

We need to traverse the list, and while traversing, if after a character node there is a number, then we need to extract that number and print the respective character the number of times equal to that extracted number.

##### Let's see the algorithm
• Traverse the list following the below steps.
• Store the character node in any variable and check for the next node.
1) If the next node is also a character that means the current character occurs only single time,
2) Else, if the next character is any value, extract that value and store that value in a variable count.
• Print the character count times.
• Now move to the next character node and repeat the above process for it.

### Dry Run    ### Code Implementation

```#include
using namespace std;

class Node {
public:
char data;
Node* next;

Node(char x) {
data = x;
next = NULL;
}
};
int count; // to store the count a particular character needs to be printed.
string decodedString = ""; // resultant string after decoding
while (current_node) {
count = 0;
char current_char = current_node->data;

//If it is not last node, we need to check for next node.
if (current_node->next) {
Node* next_node = current_node->next;

//If the next node is any numeric value , we need to extract it.
if (next_node && next_node->data >= '0' && next_node->data <= '9') {

// Why while loop ? => it can be multi-digit number also. Take an example (a->1->2->3->v->2-2). This means a occurs 123 times and v 22 times.
while (next_node && next_node->data >= '0' && next_node->data <= '9') {
count = count * 10 + (next_node->data - '0');
next_node = next_node->next;
}
current_node = next_node;
}
// If it is not numeric value, the character occurs only once. So count = 1.
else {
count = 1;
current_node = current_node->next;
}
}
//For last node.
else {
count = 1;
current_node = current_node->next;
}

//Appending the characters count times, in the resultant string.
for (int i = 0; i < count; i++) {
decodedString += current_char;
}
}

//Finally Returning the output string.
return decodedString;
}
int main() {

//To keep the implementation simple, we are adding nodes in such a way. Instead of this, we can also use append method.