{"id":4092,"date":"2021-08-20T07:25:49","date_gmt":"2021-08-20T07:25:49","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4092"},"modified":"2023-11-27T04:58:18","modified_gmt":"2023-11-27T04:58:18","slug":"rotate-a-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/rotate-a-linked-list\/","title":{"rendered":"Rotate a Linked List"},"content":{"rendered":"

\"\"
\nManipulating linked lists is a core aspect of data structures and algorithms in programming. Rotating a linked list involves rearranging its elements by shifting nodes to a specified number of positions. Understanding how to perform this operation is crucial for various applications, such as in optimizing memory usage or solving specific programming problems efficiently. This article aims to explore the concept of rotating a linked list, delve into different approaches for rotation, and provide insights into the algorithms and techniques involved in accomplishing this task.<\/p>\n

How to Rotate a Linked List?<\/h2>\n

In this question, we are given a singly linked list and an integer X. We have to rotate the list counter-clockwise by X nodes.<\/p>\n

Note: X is smaller than the count of nodes in the linked list.<\/p>\n

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

Suppose the given linked list 1 \u2192 2 \u2192 5 \u2192 10 – 12 \u2192 13, and the value of X is 4. Now, we have to rotate the given list counter-clockwise by X. <\/p>\n

Here, rotating counter-clockwise a linked list by X means that the first X nodes of the linked list will be removed from the start and get appended to the end of the list.<\/p>\n

In the given list, the first 4 nodes are 1 \u2192 2 \u2192 5 \u2192 10. Now, these 4 elements will get appended to the end of the list. So, the final list will be:
\n12 \u2192 13 \u2192 1 \u2192 2 \u2192 5 \u2192 10.<\/p>\n

In this way, we are rotating the given first X nodes counter-clockwise. <\/p>\n

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

\"\"<\/p>\n

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

\"\"<\/p>\n

Explanation :<\/strong> As the value of X is 4, so the first 4 nodes have been removed from the beginning of the linked list and appended at the end of the linked list.<\/p>\n

Now, I think from the above example, it is clear what we have to do in this problem. So let\u2019s move to approach.<\/p>\n

Before directly jumping to approach in the next section, just try to think how will approach this problem?<\/p>\n

It\u2019s okay if your solution is not the best-optimized solution, we will try to optimize it together.<\/p>\n

This question is not a very complex one. We are going to make use of linked list traversal in this question. Let us have a glance at the approach.<\/p>\n

Approach and Algorithm of rotate a linked list<\/h2>\n

The approach is going to be pretty simple.
\nLet us first think about what we need to perform the required task of rotating the list counter-clockwise by X nodes.<\/p>\n

    \n
  • For linked list rotation, we have to change the next of Xth<\/sup> node to NULL, next of the last node to the head node, and finally, make the head point to the (X+1)th<\/sup> node.<\/li>\n
  • So, we need Xth<\/sup> node, (X+1)th<\/sup> node and the last node.<\/li>\n<\/ul>\n

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

      \n
    • We will traverse through the list and stop at the Xth<\/sup> node.<\/li>\n
    • We will store the pointer to the Xth<\/sup> node.<\/li>\n
    • The (X+1)th<\/sup> node can be reached using the next of Xth<\/sup> node. Now, we will keep traversing the list till the last node, and change the pointers as stated below:\n
        \n
      • Change the next of Xth<\/sup> node to NULL<\/li>\n
      • Next of the last node to the head node.<\/li>\n
      • And finally, make the head point to the (X+1)th<\/sup> node.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n

        Dry Run of rotate a linked list<\/h3>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        Code Implementation of rotate a linked list<\/h2>\n\t\t\t\t\t\t