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.