{"id":5114,"date":"2021-10-04T11:01:39","date_gmt":"2021-10-04T11:01:39","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5114"},"modified":"2022-03-09T07:56:59","modified_gmt":"2022-03-09T07:56:59","slug":"reverse-a-doubly-linked-list-in-groups-of-given-size","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/reverse-a-doubly-linked-list-in-groups-of-given-size\/","title":{"rendered":"Reverse a doubly-linked list in groups of given size"},"content":{"rendered":"

\"\"<\/p>\n

Introduction<\/h3>\n

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.<\/p>\n<\/p>\n

Problem Statement<\/h3>\n

In this problem, we are given a Doubly Linked List and an integer X<\/strong>. We are asked to reverse the list in groups of size X<\/strong>.<\/p>\n

Problem Statement Understanding<\/h3>\n

Let\u2019s try to understand the problem statement with the help of examples.<\/p>\n

If the given doubly linked list is: 5 1 6 2 7 10 and X = 3<\/strong>.<\/p>\n

    \n
  • According to the problem statement, we have been provided a doubly-linked list, and we need to reverse the list in groups of given size i.e. every group of nodes with the size X<\/strong> needs to be reversed.<\/li>\n
  • As we can see in the above given doubly linked list there are two groups 5 1 6 (from index 0 to 2) and 2 7 10 (from index 3 to 5) of size 3 which need to be reversed.<\/li>\n
  • So after reversing the group of nodes of size 3, our output resultant doubly linked list will be 6 1 5 10 7 2.<\/li>\n<\/ul>\n

    Let’s see another example.<\/p>\n

    If the given doubly linked list is: 5 1 6 2 7 and X = 3<\/strong>.<\/p>\n

      \n
    • As we can see in the above given doubly linked list 5 1 6 is a group of nodes of size 3 and 2 7 is a group of size 2. So, we need to reverse these two group of nodes.<\/li>\n
    • After reversing the above mentioned group of nodes, our resultant doubly linked list will be 6 1 5 7 2<\/li>\n<\/ul>\n

      Note:<\/strong> Suppose we were asked to reverse every group of nodes of size X<\/strong> in a doubly linked list. If in case there remains a group of nodes at the end of the linked list which has size smaller than X, then irrespective of its size we will reverse it in similar way as we were reversing nodes of group of size X.<\/p>\n

      Now I think from the above examples, the problem is clear. So let\u2019s see how we can approach it.<\/p>\n

      Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n

        \n
      • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.<\/li>\n<\/ul>\n

        Let\u2019s move to the approach section.<\/p>\n

        Approach<\/h3>\n

        Our approach will be recursive:<\/p>\n

          \n
        • Here the main idea will be to use recursion to reverse the Doubly Linked List in group of given size, and after reversing a group, we need to call the function again for the next group of nodes if the next node is not null. <\/li>\n
        • The function will be called recursively until there are no elements left to be reversed.<\/li>\n
        • After the recursion is over, we will have our doubly linked list reversed in group of given size.<\/li>\n<\/ul>\n

          Algorithm<\/h3>\n

          1) Our recursive function reverseListInGroupOfX()<\/strong> will receive the first node of every group of size X<\/strong> of the doubly linked list.
          \n2) For every group of nodes in the recursive function reverseListInGroupOfX()<\/strong>:<\/p>\n

            \n
          • First, we will reverse the nodes in the current group.<\/li>\n
          • After the nodes of the current group have been reversed, we will check whether the next group of nodes exists or not:\n
              \n
            • If the next group of nodes exists, we will perform the same steps for the next group of nodes that we are performing for the current group.<\/li>\n
            • Also, for the current group of nodes, we need to link the next and the prev links of a group properly with the next group of nodes and previous group of nodes.<\/li>\n<\/ul>\n<\/li>\n
            • Finally, we will return the new head of the group.
              \n3) Following all these above steps until all the group of nodes have been reversed, we will get our resultant doubly linked list.<\/li>\n<\/ul>\n

              Dry Run<\/h3>\n

              \"\"<\/p>\n

              \"\"<\/p>\n

              \"\"<\/p>\n

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