{"id":4245,"date":"2021-08-24T11:49:49","date_gmt":"2021-08-24T11:49:49","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4245"},"modified":"2022-11-22T09:10:27","modified_gmt":"2022-11-22T09:10:27","slug":"rotate-doubly-linked-list-by-n-nodes","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/rotate-doubly-linked-list-by-n-nodes\/","title":{"rendered":"Rotate Doubly linked list by N nodes"},"content":{"rendered":"

\"\"<\/p>\n

Most of the linked list questions are not that complicated as they seem because a normal logic can be applied. Lets just say we have to rotate doubly linked list by n nodes. To approach this code, we will simply make the last node pointed to the head of the first node and make it circular. And then we will remove the next pointer after n nodes and to make it un-circular. So, in this article, let’s get into the approach to rotate doubly linked list by n nodes.<\/p>\n

How to Rotate Doubly Linked List by N Nodes<\/h2>\n

In this problem, we have been given a doubly linked list. Our task is to rotate the linked list counter-clockwise by N nodes. Here, N is a given positive integer which is smaller than the total number of nodes in the doubly linked list.<\/p>\n

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

For example, if the doubly linked list is:<\/p>\n

\"\"<\/p>\n

and let’s assume N to be equal to 2. <\/p>\n

So according to the problem statement now we have to rotate the doubly linked list counter-clockwise by 2 nodes. To do, so the nodes with value A and B will be removed from their original positions and will be inserted at the end of the linked list, which will yield us our final resultant linked list as:<\/p>\n

\"\"<\/p>\n

Given list:<\/p>\n

\"\"<\/p>\n

Rotated list:<\/p>\n

\"\"<\/p>\n

Similarly, if we are given a linked list as:<\/p>\n

\"\"<\/p>\n

It means that we will have to rotate the above doubly linked list counter-clockwise by 4 nodes. To do, so we will move the first 4 nodes from the beginning to the end of the list such that our final linked list will be:<\/p>\n

\"\"<\/p>\n

Some more Examples<\/h4>\n

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

\"\"<\/p>\n

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

\"\"<\/p>\n

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

\"\"<\/p>\n

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

\"\"<\/p>\n

Now I think from the above examples it is clear what the problem is demanding. So next we have to think how we can approach this problem towards a solution?<\/p>\n

Let\u2019s have a glance at approach.<\/p>\n

Approach and Algorithm to rotate doubly linked list by n nodes<\/h2>\n

The approach is going to be pretty simple.
\nSo let\u2019s first think about what we actually need to perform the task of rotating a doubly linked list by N nodes.<\/p>\n

    \n
  1. To rotate the doubly linked list by N nodes\n
      \n
    • We need to change the next pointer of Nth<\/sup> node to NULL.<\/li>\n
    • Next pointer of last node (i.e. Last node of the doubly linked list) to head node.<\/li>\n
    • prev of head node to last node.<\/li>\n
    • And finally change head to (N+1)th<\/sup> node and prev of new head node to NULL (Since we know that in a doubly linked list, prev of head node is NULL).<\/li>\n<\/ul>\n<\/li>\n
    • So we basically need to get hold of these three nodes: Nth<\/sup> node, (N+1)th<\/sup> node and last node.<\/li>\n<\/ol>\n

      To achieve the above objective of rotation:<\/strong><\/p>\n

        \n
      1. Start traversing the list from the beginning and stop at the Nth<\/sup> node.<\/li>\n
      2. Store the pointer to Nth<\/sup> node so that we can get (N+1)th<\/sup> node using NthNode->next.<\/li>\n
      3. We will keep traversing the list till the end of the list and store the pointer to the last node as well.<\/li>\n
      4. Finally, we will change the pointers as stated below.\n
          \n
        • Change the next pointer of Nth node to NULL.<\/li>\n
        • Make next pointer of last node point to the head node<\/li>\n
        • Make prev of head node point to the to last node.<\/li>\n
        • Finally, make (N+1)th<\/sup> node the new head and point the prev of new head node to NULL.<\/li>\n<\/ul>\n<\/li>\n
        • Finally, following the above steps, our list will get rotated counter-clockwise by N nodes.<\/li>\n<\/ol>\n

          At last, print the rotated list using the PrintList function. <\/p>\n

          Dry Run to rotate doubly linked list by n nodes<\/h3>\n

          \"\"
          \n\"\"<\/p>\n

          Code Implementation to rotate doubly linked list by n nodes<\/h2>\n\t\t\t\t\t\t