{"id":2027,"date":"2020-07-01T09:51:36","date_gmt":"2020-07-01T09:51:36","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2027"},"modified":"2022-11-28T10:01:08","modified_gmt":"2022-11-28T10:01:08","slug":"list-reduction","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/list-reduction\/","title":{"rendered":"List Reduction"},"content":{"rendered":"

\"\"<\/p>\n

This blog Discusses the famous question \u201clist reduction in linked list\u201d. Linked list reduction plays an important role in improving your data structures like linked list. In linked list reduction, we have to remove the nodes. Criteria for removing nodes is the nodes with the same data and are next to each other will be removed from the linked list. Let\u2019s discuss the reduction list in detail.<\/p>\n

Linked List Reduction:<\/h2>\n
\n

Given a linked list of N<\/code> nodes such that each node have a lower case alphabet (a - z)<\/code>. Your task is to remove the nodes which have the same data and are next to each other.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/strong><\/p>\n

Input : bddbcgdghgii\n\nOutput: cgdghg\n\nExplanation : bddbcgdghgii -> bbcgdghg -> cgdghg<\/code><\/pre>\n
SOLVING APPROACH For Linked List Reduction:<\/h2>\n
    \n
  1. \n
    The idea is to create another list temp<\/code> to store the reduced version of the original list.<\/p>\n<\/li>\n
  2. \n
    Traverse the original list and perform the following operations:<\/p>\n
      \n
    • If the temp<\/code> list is empty, simply append the current element into the list.<\/li>\n
    • If the temp<\/code> list is not empty, check if the last element inserted is equal to the current element, If Yes<\/code> remove the last element added.<\/li>\n
    • Else if the last element is not equal to the current element, append the current element into the list. Finally our original list will be reduced and stored in the temp<\/code> list.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n
      ILLUSTRATION For Linked List Reduction:<\/h3>\n
      list = bddbcgdghgii\ntemp is empty\n\nStart traversing the list :-\n\nfor 1st element b, temp is empty so append into it \ntemp = b\n\nfor 2nd element d, b is not equal to d so append into it\ntemp = bd\n\nfor 3rd element d, d is equal to d so remove already added d\ntemp = b\n\nfor 4th element b, b is equal to b so remove already added b, temp becomes empty now\ntemp = \n\nfor 5th element c, temp is empty so append into it\ntemp = c\n\nfor 6th element g, g is not equal to c so append into it\ntemp = cg\n\nfor 7th element d, d is not equal to g so append into it\ntemp = cgd\n\nfor 8th element g, g is not equal to d so append into it\ntemp = cgdg\n\nfor 9th element h, h is not equal to g so append into it\ntemp = cgdgh\n\nfor 10th element g, g is not equal to h so append into it\ntemp = cgdghg\n\nfor 11th element i, i is not equal to g so append into it\ntemp = cgdghgi\n\nfor 12th element i, i is equal to i so remove already added i\ntemp = cgdghg\n\nSo, our final reduced list is cgdghg<\/code><\/pre>\n
      SOLUTIONS For Linked List Reduction:<\/h2>\n\t\t\t\t\t\t