Given a Linked List as the input. The task is to encode the given linked list using Run Length Encoding. That is, to replace a block of contiguous characters by the character followed by it’s count.
For Example, in Run Length Encoding “a->a->a->a->a” will be replaced by “a->5”.
Note: For non-repeating nodes, do not append count 1. For example, a->b->b will be replaced by “a->b->2” and not “a->1->b->2”.
Examples:
Input : List = a->a->a->a->a->b->r->r->r->NULL
Output : a->5->b->r->3->NULL
Explanation :
The character ‘a’ repeats 5 times.
The character ‘b’ repeats 1 time.
The character ‘r’ repeats 3 times.
Hence the output is a->5->b->r->3->NULL.Input : a->a->a->a->a->a->a->a->a->a->b->r->r->r->a->a->a->NULL
Output : a->1->0->b->r->3->a->3->NULL
Approach:
- Traverse through the list.
- Consider the first character as c.
- Consider the current character as x.
- If the character is the same as c then increment the count.
- If the characters are not same then add the count to the list and append the next character to the list reset the count to 1.
Implementation:
C++
// C++ program to encode a linked list// using Run Length Encoding#include <bits/stdc++.h>using namespace std;// A linked list nodestruct Node { char data; struct Node* next; Node(int x) { data = x; next = NULL; }};// Function to append nodes to a listvoid append(struct Node* head_ref, char new_data){ struct Node* new_node = new Node(new_data); struct Node* last = head_ref; if (head_ref == NULL) { head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return;}// Function to print listvoid printList(Node* node){ while (node != NULL) { cout << node->data << " "; node = node->next; }}// Function to encode the listvoid RLE(Node* head){ // Pointer used to traverse through // all the nodes in the list Node* p = head; // List to store the encoded message Node* temp = new Node(p->data); // Store the first character in c char c = p->data; p = p->next; // Count to count the number of // continuous elements int count = 1; // Traverse through all the // elements in the list while (p != NULL) { // Store the current character in x char x = p->data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append(temp, '0' + (count / 10)); append(temp, '0' + (count % 10)); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p->next; } // Add the final count if (count != 0) append(temp, '0' + count); // Print the list printList(temp);}// Driver codeint main(){ // Creating the linked list Node* head = new Node('a'); head->next = new Node('a'); head->next->next = new Node('a'); head->next->next->next = new Node('b'); head->next->next->next->next = new Node('r'); head->next->next->next->next->next = new Node('r'); RLE(head); return 0;} |
Java
// Java program to encode a linked list// using Run Length Encodingclass GFG {// A linked list nodestatic class Node { char data; Node next;};// Utility function to create a new Nodestatic Node newNode(char data){ Node temp = new Node(); temp.data = data; temp.next = null; return temp;}// Function to append nodes to a liststatic void append(Node head_ref, char new_data){ Node new_node = newNode(new_data); Node last = head_ref; if (head_ref == null) { head_ref = new_node; return; } while (last.next != null) last = last.next; last.next = new_node; return;}// Function to print liststatic void printList(Node node){ while (node != null) { System.out.print(node.data+" "); node = node.next; }}// Function to encode the liststatic void RLE(Node head){ // Pointer used to traverse through // all the nodes in the list Node p = head; // List to store the encoded message Node temp = newNode(p.data); // Store the first character in c char c = p.data; p = p.next; // Count to count the number of // continuous elements int count = 1; // Traverse through all the // elements in the list while (p != null) { // Store the current character in x char x = p.data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append(temp, (char) ('0' + (count / 10))); append(temp, (char) ('0' + (count % 10))); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p.next; } // Add the final count if (count != 0) append(temp, (char) ('0' + count)); // Print the list printList(temp);}// Driver codepublic static void main(String[] args) { // Creating the linked list Node head = newNode('a'); head.next = newNode('a'); head.next.next = newNode('a'); head.next.next.next = newNode('b'); head.next.next.next.next = newNode('r'); head.next.next.next.next.next = newNode('r'); RLE(head); }}// This code has been contributed by 29AjayKumar |
Python3
# Python3 program to encode a linked list# using Run Length Encoding # A linked list nodeclass Node: def __init__(self, data): self.data = data self.next = None # Function to append nodes to a listdef append(head_ref, new_data): _node = Node(new_data); last = head_ref; if (head_ref == None): head_ref =_node; return; while (last.next != None): last = last.next; last.next =_node; return; # Function to print listdef printList(node): while (node != None): print(node.data, end = ' ') node = node.next; # Function to encode the listdef RLE(head): # Pointer used to traverse through # all the nodes in the list p = head; # List to store the encoded message temp = Node(p.data); # Store the first character in c c = p.data; p = p.next; # Count to count the number of # continuous elements count = 1; # Traverse through all the # elements in the list while (p != None): # Store the current character in x x = p.data; # If the characters are same if (c == x): # Increment count count += 1 # Else else: # If the count is greater than 1 if (count > 1): # Append the count to list if (count > 9): append(temp, chr(ord('0') + (count // 10))); append(temp, chr(ord('0') + (count % 10))); # Reset the count count = 1; # Add the next character # to the list append(temp, x); # Take the character to check as # the current character c = x; p = p.next; # Add the final count if (count != 0): append(temp, chr(ord('0') + count)) # Print the list printList(temp); # Driver codeif __name__=='__main__': # Creating the linked list head = Node('a'); head.next = Node('a'); head.next.next = Node('a'); head.next.next.next = Node('b'); head.next.next.next.next = Node('r'); head.next.next.next.next.next = Node('r'); RLE(head); # This code is contributed by pratham76 |
C#
// C# program to encode a linked list// using Run Length Encodingusing System;class GFG {// A linked list nodepublic class Node { public char data; public Node next;};// Utility function to create a new Nodestatic Node newNode(char data){ Node temp = new Node(); temp.data = data; temp.next = null; return temp;}// Function to append nodes to a liststatic void append(Node head_ref, char new_data){ Node new_node = newNode(new_data); Node last = head_ref; if (head_ref == null) { head_ref = new_node; return; } while (last.next != null) last = last.next; last.next = new_node; return;}// Function to print liststatic void printList(Node node){ while (node != null) { Console.Write(node.data+" "); node = node.next; }}// Function to encode the liststatic void RLE(Node head){ // Pointer used to traverse through // all the nodes in the list Node p = head; // List to store the encoded message Node temp = newNode(p.data); // Store the first character in c char c = p.data; p = p.next; // Count to count the number of // continuous elements int count = 1; // Traverse through all the // elements in the list while (p != null) { // Store the current character in x char x = p.data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append(temp, (char) ('0' + (count / 10))); append(temp, (char) ('0' + (count % 10))); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p.next; } // Add the final count if (count != 0) append(temp, (char) ('0' + count)); // Print the list printList(temp);}// Driver codepublic static void Main() { // Creating the linked list Node head = newNode('a'); head.next = newNode('a'); head.next.next = newNode('a'); head.next.next.next = newNode('b'); head.next.next.next.next = newNode('r'); head.next.next.next.next.next = newNode('r'); RLE(head);}}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript program to encode a linked list // using Run Length Encoding // A linked list node class Node { constructor() { this.data = 0; this.next = null; } } // Utility function to create a new Node function newNode(data) { var temp = new Node(); temp.data = data; temp.next = null; return temp; } // Function to append nodes to a list function append(head_ref, new_data) { var new_node = newNode(new_data); var last = head_ref; 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 function printList(node) { while (node != null) { document.write(node.data + " "); node = node.next; } } // Function to encode the list function RLE(head) { // Pointer used to traverse through // all the nodes in the list var p = head; // List to store the encoded message var temp = newNode(p.data); // Store the first character in c var c = p.data; p = p.next; // Count to count the number of // continuous elements var count = 1; // Traverse through all the // elements in the list while (p != null) { // Store the current character in x var x = p.data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append( temp, String.fromCharCode("0".charCodeAt(0) + parseInt(count / 10)) ); append( temp, String.fromCharCode("0".charCodeAt(0) + (count % 10)) ); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p.next; } // Add the final count if (count != 0) append(temp, String.fromCharCode("0".charCodeAt(0) + count)); // Print the list printList(temp); } // Driver code // Creating the linked list var head = newNode("a"); head.next = newNode("a"); head.next.next = newNode("a"); head.next.next.next = newNode("b"); head.next.next.next.next = newNode("r"); head.next.next.next.next.next = newNode("r"); RLE(head); </script> |
Output
a 3 b r 2
Complexity Analysis:
- Time Complexity: O(N2)
- Auxiliary Space: O(1)
In Place Conversion:
The idea here is to modify the existing list based on the frequency of characters rather than creating a new list if system enforces space constraint.
- Traverse through the list.
- Compare current character with the next character. If same then increment the count value.
- Delete nodes whose frequency is greater than 2.
- If characters are not same, then update the count value.
C++
// C++ program implementing run length encoding#include<stdio.h>#include<stdlib.h>struct Node{ char data; struct Node* next; Node(int x) { data = x; next = NULL; }};// Function to add node to the listNode* insert (Node *head, int data){ if (head == NULL) return new Node(data); head->next = insert(head->next, data); return head;}// Function to print the listvoid printList (Node* head){ while (head != NULL) { printf ("%c ",head->data); head = head->next; } return;}void runLengthEncode (Node* head){ Node* temp = NULL; Node* ptr = NULL; int count = 0; //count the number of characters temp = head; while (temp != NULL) { ptr = temp; count = 1; //check if current data and next data is same.If same, then increment count while (temp->next != NULL && temp->data == temp->next->data) { count++; if (count > 2) { // delete only when the node value is repeated more than // twice. ptr->next = temp->next; free(temp); temp = ptr; } temp = temp->next; } // update only when the node value is repeated more than one time. if (count > 1) temp->data = count + '0'; temp = temp->next; } return;}// Driver codeint main(){ // Creating the linked list Node* head = new Node('a'); head->next = new Node('a'); head->next->next = new Node('a'); head->next->next->next = new Node('b'); head->next->next->next->next = new Node('r'); head->next->next->next->next->next = new Node('r'); runLengthEncode (head); printList (head); return 0;} |
Java
// java program implementing run length encodingclass GFG { // A linked list node 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 add node to the list static Node insert(Node head, char data) { if (head == null) return newNode(data); head.next = insert(head.next, data); return head; } // Function to print the list static void printList (Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } return; } static void runLengthEncode (Node head) { Node temp; Node ptr; int count = 0; //count the number of characters temp = head; while (temp != null) { ptr = temp; count = 1; //check if current data and next data is same.If same, then increment count while (temp.next != null && temp.data == temp.next.data) { count++; if (count > 2) { // delete only when the node value is repeated more than // twice. ptr.next = temp.next; temp= null; temp = ptr; } temp = temp.next; } // update only when the node value is repeated more than one time. if (count > 1) temp.data = (char) (count + '0'); temp = temp.next; } return; } // Driver code public static void main(String [] args) { // Creating the linked list Node head = newNode('a'); head.next = newNode('a'); head.next.next = newNode('a'); head.next.next.next = newNode('b'); head.next.next.next.next = newNode('r'); head.next.next.next.next.next = newNode('r'); runLengthEncode (head); printList (head); } }// This code is contributed by AR_Gaurav |
Python3
# Python3 program implementing run length encodingclass Node: def __init__(self, data): self.data = data self.next = None# Function to add node to the listdef insert(head, data): if (head == None): return Node(data); head.next = insert(head.next, data); return head;# Function to print the listdef printList(head): while (head != None): print(head.data, end = ' ') head = head.next; return;def runLengthEncode(head): temp = None; ptr = None; count = 0; #count the number of characters temp = head; while (temp != None): ptr = temp; count = 1; # check if current data and next data # is same.If same, then increment count while (temp.next != None and temp.data == temp.next.data): count += 1 if (count > 2): # delete only when the node # value is repeated more than # twice. ptr.next = temp.next; del (temp); temp = ptr; temp = temp.next; # update only when the node value # is repeated more than one time. if (count > 1): temp.data = count ; temp = temp.next; return;# Driver codeif __name__=='__main__': # Creating the linked list head = Node('a'); head.next = Node('a'); head.next.next = Node('a'); head.next.next.next = Node('b'); head.next.next.next.next = Node('r'); head.next.next.next.next.next = Node('r'); runLengthEncode(head); printList(head); # This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program implementing // run length encodingclass Node{ constructor(x) { this.data=x; this.next=null; }}// Function to add node to the listfunction insert (head,data){ if (head == null) return new Node(data); head.next = insert(head.next, data); return head;}// Function to print the listfunction printList (head){ while (head != null) { document.write(head.data+" "); head = head.next; } return;}function runLengthEncode (head){ let temp = null; let ptr = null; let count = 0; //count the number of characters temp = head; while (temp != null) { ptr = temp; count = 1; //check if current data and next data is same.If same, // then increment count while (temp.next != null && temp.data == temp.next.data) { count++; if (count > 2) { // delete only when the node value // is repeated more than // twice. ptr.next = temp.next; delete(temp); temp = ptr; } temp = temp.next; } // update only when the node value is // repeated more than one time. if (count > 1) temp.data = count ; temp = temp.next; } return;}// Driver codelet head = new Node('a');head.next = new Node('a');head.next.next = new Node('a');head.next.next.next = new Node('b');head.next.next.next.next = new Node('r');head.next.next.next.next.next = new Node('r');runLengthEncode (head);printList (head);// This code is contributed by unknown2108</script> |
Output
a 3 b r 2
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
