Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Run Length Decoding in Linked List

Last Updated on March 9, 2022 by Ria Pathak

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

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

### Code Implementation

```#include<bits stdc++.h="">
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.

}
```
```class Decode
{
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();

new_node.data = new_data;

new_node.next = null;

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
{
// Pointer used to traverse through all
// the nodes in the list

// 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[])
{

}
}

```
```# 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
new_node = Node;
new_node.data = new_data;
new_node.next = None;
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
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;

if __name__=='__main__':