{"id":4249,"date":"2021-08-24T17:18:22","date_gmt":"2021-08-24T17:18:22","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4249"},"modified":"2022-03-09T08:05:03","modified_gmt":"2022-03-09T08:05:03","slug":"run-length-decoding-in-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/run-length-decoding-in-linked-list\/","title":{"rendered":"Run Length Decoding in Linked List"},"content":{"rendered":"

\"\"<\/p>\n

Introduction<\/h3>\n

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.<\/p>\n<\/p>\n

Problem Statement<\/h3>\n

We will be provided with a Linked List in encoded form (like a4de4f2<\/strong>) and we need to decode the given linked list and output the decoded version in the form of string.<\/p>\n

Example<\/h5>\n

Input Linked List :<\/strong> <\/p>\n

\"\"<\/p>\n

Output String :<\/strong> aaaadeeeeff<\/p>\n

Problem Statement Understanding<\/h3>\n

Giving you a brief description about run length encoding. <\/p>\n

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.<\/p>\n

For example<\/strong><\/p>\n

    \n
  • If the input string is aaaa<\/strong> then its run length encoding will be a4<\/strong><\/li>\n
  • If we add dd<\/strong> to the above string aaaa<\/strong> then the resultant string will be aaaadd<\/strong> and now its run length encoding will become a4d2<\/strong>.<\/li>\n
  • Similarly, if we add eee<\/strong> to the string aaaadd<\/strong> then the resultant string will be aaaaddeee<\/strong> and now its run length encoding will become a4d2e3<\/strong>.<\/li>\n
  • But there is case like if we add a single character to the like f<\/strong> to the string aaaaddeee<\/strong>, then the resultant string will be aaaaddeeef<\/strong> and its run length encoding will be a4d2e3f<\/strong>.<\/li>\n<\/ul>\n

    I think from the above pattern you got it how we are encoding the input string.<\/p>\n

    Example of Run Length Encoding<\/h4>\n

    Input String<\/strong> – aaaadeeeeff
    \nOutput String (Encoded Using Run Length Algorithm)<\/strong> – a4de4f2<\/p>\n

    Now, since you have understood what Run length encoding is, let us move to our problem statement description.<\/p>\n

    We will be provided with a Linked List in encoded form (like a4de4f2<\/strong>) and we need to decode the given linked list and output the decoded version in the form of a string.<\/p>\n

    Considering same example for run length decoding<\/h4>\n

    Input Linked List :<\/strong><\/p>\n

    \"\"<\/p>\n

    Output String :<\/strong> aaaadeeeeff<\/p>\n

    Explanation :<\/strong> Given a linked list a \u2192 4 \u2192 d \u2192 e \u2192 4 \u2192 f \u2192 2, which means that:<\/p>\n

      \n
    • a<\/strong> occur 4 times. <\/li>\n
    • d<\/strong> occur only once because following d<\/strong> there is no count i.e. the next node does not contain any digit representing the count of d<\/strong>.<\/li>\n
    • e<\/strong> occurs 4 times. <\/li>\n
    • f<\/strong> occurs 2 times. <\/li>\n<\/ul>\n

      Therefore, in output you need to print a string containing 4 times a<\/strong>, 1 time d<\/strong> , 4 times e<\/strong> and 2 times f<\/strong>, i.e., "aaaadeeeeff", which is our output.<\/p>\n

      Approach and Algorithm<\/h3>\n

      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.<\/p>\n

      Let’s see the algorithm<\/h5>\n
        \n
      • Traverse the list following the below steps.<\/li>\n
      • Store the character node in any variable and check for the next node.
        \n1) If the next node is also a character that means the current character occurs only single time,
        \n2) Else, if the next character is any value, extract that value and store that value in a variable count.<\/li>\n
      • Print the character count times.<\/li>\n
      • Now move to the next character node and repeat the above process for it.<\/li>\n<\/ul>\n

        Dry Run<\/h3>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        Code Implementation<\/h3>\n\t\t\t\t\t\t