---
Difficulty: Medium
Source: 160 Days of Problem Solving
Tags:
- Linked-List
---
# π _Day 2. Rotate a linked list_ π§
The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/linked-list-gfg-160/problem/rotate-a-linked-list)
## π‘ **Problem Description:**
You are given the head of a singly linked list and an integer `k`. Your task is to left-rotate the linked list `k` times.
## π **Example Walkthrough:**
**Input:**
`head = 10 -> 20 -> 30 -> 40 -> 50`, `k = 4`
**Output:**
`50 -> 10 -> 20 -> 30 -> 40`
**Explanation:**
Rotate 1: `20 -> 30 -> 40 -> 50 -> 10`
Rotate 2: `30 -> 40 -> 50 -> 10 -> 20`
Rotate 3: `40 -> 50 -> 10 -> 20 -> 30`
Rotate 4: `50 -> 10 -> 20 -> 30 -> 40`
**Input:**
`head = 10 -> 20 -> 30 -> 40`, `k = 6`
**Output:**
`30 -> 40 -> 10 -> 20`
**Explanation:**
Since `k = 6` exceeds the length of the list (`4`), `k` is reduced to `k % length = 2`. After two left rotations:
`10 -> 20 -> 30 -> 40` β `20 -> 30 -> 40 -> 10` β `30 -> 40 -> 10 -> 20`.
### Constraints:
- $`1 <= number of nodes <= 10^5`$
- $`0 <= k <= 10^9`$
- $`0 <= data of node <= 10^9`$
## π― **My Approach:**
1. **Key Observations:**
- If `k` is greater than the length of the list, we only need to perform `k % length` rotations, as rotating the list `length` times results in the same list.
- Breaking the linked list into two parts and re-linking the tail to the head helps achieve the rotation efficiently.
2. **Algorithm:**
- Compute the length of the list (`len`).
- Reduce `k` to `k % len` to handle large values of `k`.
- If `k = 0`, return the original list as no rotation is required.
- Traverse the list to find the new tail (the node at position `len - k`) and the new head (the node at position `len - k + 1`).
- Break the list into two parts by setting the `next` pointer of the new tail to `nullptr`.
- Re-link the old tail to the original head.
- Return the new head.
## π **Time and Auxiliary Space Complexity**
- **Expected Time Complexity:** O(n), where `n` is the length of the linked list. This is because we traverse the list twice: once to calculate its length and once to locate the new head and tail.
- **Expected Auxiliary Space Complexity:** O(1), as no additional space is used apart from a few pointers.
## π **Solution Code**
## Code (C++)
```cpp
class Solution {
public:
Node* rotate(Node* head, int k) {
if (!head || !head->next || !k) return head;
int len = 1;
Node* tail = head;
while (tail->next) tail = tail->next, len++;
k %= len;
if (!k) return head;
Node* newTail = head;
for (int i = 1; i < k; i++) newTail = newTail->next;
Node* newHead = newTail->next;
newTail->next = nullptr;
tail->next = head;
return newHead;
}
};
```
π¨βπ» Alternative Approach
### **Alternative Approach: Optimized Left Rotation**
The idea is similar but involves fewer intermediate calculations. We aim to find the breaking point in one traversal. Here's the implementation:
```cpp
class Solution {
public:
Node* rotate(Node* head, int k) {
if (!head || !head->next || k == 0) {
return head;
}
int len = 1;
Node* tail = head;
while (tail->next) {
tail = tail->next;
len++;
}
k %= len;
if (k == 0) {
return head;
}
Node* newTail = head;
for (int i = 1; i < k; i++) { // LEFT rotation
newTail = newTail->next;
}
Node* newHead = newTail->next;
newTail->next = nullptr;
tail->next = head;
return newHead;
}
};
```
## Code (Java)
```java
class Solution {
public Node rotate(Node head, int k) {
if (head == null || head.next == null || k == 0) return head;
int len = 1;
Node tail = head;
while (tail.next != null) {
tail = tail.next;
len++;
}
k %= len;
if (k == 0) return head;
Node newTail = head;
for (int i = 1; i < k; i++) {
newTail = newTail.next;
}
Node newHead = newTail.next;
newTail.next = null;
tail.next = head;
return newHead;
}
}
```
## Code (Python)
```python
class Solution:
def rotate(self, head, k):
if k == 0 or head is None:
return head
curr = head
length = 1
while curr.next is not None:
curr = curr.next
length += 1
k %= length
if k == 0:
curr.next = None
return head
curr.next = head
curr = head
for _ in range(1, k):
curr = curr.next
newHead = curr.next
curr.next = None
return newHead
```
## π― **Contribution and Support:**
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
---
πVisitor Count
