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.

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

#include<bits stdc++.h=""> using 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); }

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(); 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[]) { Node head = newNode('a'); head.next = newNode('4'); head.next.next = newNode('d'); head.next.next.next = newNode('e'); head.next.next.next.next = newNode('4'); head.next.next.next.next.next = newNode('f'); head.next.next.next.next.next.next = newNode('2'); System.out.println(decodeList(head)); } }

# 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; if __name__=='__main__': # Creating the linked list head = newNode('a'); head.next = newNode('4'); head.next.next = newNode('d'); head.next.next.next = newNode('e'); head.next.next.next.next = newNode('4'); head.next.next.next.next.next = newNode('f'); head.next.next.next.next.next.next = newNode('2'); print(decodeList(head))

#### Output

aaaadeeeeff

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

[forminator_quiz id=”4251″]

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.