Rotate a Linked List I GFG I POTD I CPP CodeI DSA I Problem of the day I Linkedlist #gfg #potd

Code Explanation: Input: The function takes the head of a linked list and an integer k as input. The goal is to rotate the linked list by k positions. Step 1 - Store List Elements in an Array: An array is created to store the elements of the linked list. A temporary pointer is used to go through the linked list, adding each element to the array. The loop continues until the end of the list is reached. Step 2 - Adjust Rotation Count: The size of the array is stored in a variable n, which tells the number of elements in the linked list. The value of k is adjusted using the modulus operation: k equals k divided by n. This ensures that rotating the list by a number larger than the list size will still work correctly. Step 3 - Reverse Subarrays: The rotation is done by reversing parts of the array: First, the first k elements of the array are reversed. Then, the remaining elements after k are reversed. Finally, the entire array is reversed to get the desired rotated order. Step 4 - Rebuild the Rotated Linked List: A new linked list is created from the modified array. A new node is created using the first element of the array and becomes the head of the new linked list. The other elements are added to the new list by going through the array and creating new nodes. Return: The new head of the rotated linked list is returned. Example: If we have a linked list with values 1, 2, 3, 4, 5, and we want to rotate it by 2 positions: Store the elements in an array: [1, 2, 3, 4, 5] Adjust the value of k: k equals 2 modulo 5, which is 2. Reverse the array: Reverse the first 2 elements: [2, 1, 3, 4, 5] Reverse the remaining elements: [2, 1, 5, 4, 3] Reverse the entire array: [3, 4, 5, 1, 2] Rebuild the linked list from the array: 3, 4, 5, 1, 2 The rotated linked list is returned. Time Complexity: Storing the linked list in an array takes linear time. Reversing the array parts takes linear time. Rebuilding the linked list takes linear time. Thus, the total time complexity is linear. Space Complexity: The space used by the array is linear in size. This method uses extra space to store the list elements, but the logic is simple and works efficiently for rotating the list.