### 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

**Input Linked List :**

**Output String :** aaaadeeeeff

### 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

**Input String** - aaaadeeeeff

**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

**Input Linked List :**

**Output String :** aaaadeeeeff

**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

#includeusing namespace std; class Node { public: char data; Node* next; Node(char x) { data = x; next = NULL; } }; string decodeList(Node* head) { Node* current_node = head; 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() { Node* head = new Node('a'); head->next = new Node('4'); head->next->next = new Node('d'); head->next->next->next = new Node('e'); head->next->next->next->next = new Node('4'); head->next->next->next->next->next = new Node('f'); head->next->next->next->next->next->next = new Node('2'); //To keep the implementation simple, we are adding nodes in such a way. Instead of this, we can also use append method. cout << decodeList(head); }

#### Output

aaaadeeeeff

**Time Complexity:** O(n), where n is the number of nodes in the given LinkedList.

This blog tried to discuss the problem when we are given an encoded string in the form of linkedlist and we were required to decode it. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.