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

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
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);
}

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.

Previous post Introduction to Unrolled Linked List
Next post Sort a linked list of 0s, 1s, and 2s by changing links

Leave a Reply

Your email address will not be published. Required fields are marked *