🌀 Rotating List by K Places

---

🧩 The Problem:

Given a singly linked list, rotate it to the right by k nodes.

Example: If the list is 1 → 2 → 3 → 4 → 5 → NULL
and k = 2 then,
rotate 1: 5 → 1 → 2 → 3 → 4 → NULL

rotate 2: 4 → 5 → 1 → 2 → 3 → NULL

the rotated list becomes( final output ):
4 → 5 → 1 → 2 → 3 → NULL

---

💡 Key Insight

For me, the key challenge was identifying the exact condition that ensures the rotation works correctly.

• I realized that when k == n (total nodes), no rotation is needed.

• And if k > n, it loops back. So, k = k % n simplifies the problem.

---

🛠️ Steps I Took:

1. Count the number of nodes n

2. Update k = k % n to handle big k

3. Make the list circular by connecting the last node to the head

4. Find the new tail → it's the (n - k)th node

5. Break the circle and update head (n-k+1)th node

---

🧪 The Code (C++)

void rotateNOdesByK(node *&head, int k)
{
    if (!head || !head->next || k == 0) return head; // edge case(mandatory for leetCode)
    node *temp = head;
    int n = 1;
    while (temp->next != nullptr)
    {
        temp = temp->next;
        n++;
    }

    k = k % n; // to handle large k; 
    if (k == 0) return; // no rotation needed;

    temp->next = head; // Step 3: Make it circular

    temp = head;
    for (int i = 1; i < (n - k); i++) // to reach at (n-k)th node; 
    {
        temp = temp->next;
    }

    node *newHead = temp->next; // (n-k+1)th node
    temp->next = nullptr;       // (n-k)th node
    head = newHead;
}

---

🔍 LeetCode Tip : Avoid Runtime Errors on Edge Cases (must)

When solving linked list problems on platforms like LeetCode, don’t forget to handle these edge cases up front, or you'll face runtime errors.

if (!head || !head->next || k == 0) return head;

🧠 Always remember:

“Edge cases are not extras, they’re entry tests!”

---

🧠 Key Takeaways:

• Always do k = k % n when dealing with rotations—it’s a lifesaver.

• Turning the list into a temporary circle makes the shifting logic easier.

• Break down the problem into smaller steps—it makes implementation clean and less buggy.

---

Time and Space Complexity( step-by-step ):

✅ Time Complexity: O(n)

1. Counting the number of nodes (n) — O(n)

2. Connecting the last node to the head — O(1)

3. Traversing to the (n - k)th node — O(n) in the worst case

Even though we have two separate traversals, they’re both linear with respect to the size of the list, so:

Total Time = O(n)

✅ Space Complexity: O(1)

Not used any extra space (no array, no map, etc.), just a few pointers (temp, newHead) and counters.

Total Space = O(1)

Complexities:

---

Let me know your thoughts, and feel free to try rotating your own linked list with different values of k—the intuition gets better the more you visualize it!

---

💻 Keep coding, 🚀 keep optimizing!