Practice › Linked List
Rotate List
Medium · Linked List · Asked at Amazon, Microsoft, LinkedIn
Rotate the list to the right by k places (the last k nodes move to the front).
Input
First line: n. Second line: n values. Third line: k.
Output
The rotated list, space-separated.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ k ≤ 2·10^9
Find the length, make it circular, and break it at the right place. Remember k % n.
Example 1
Input
5 1 2 3 4 5 2
Output
4 5 1 2 3
Example 2
Input
3 0 1 2 4
Output
2 0 1
Hints
- Rotating by n gives back the same list, so use k % n.
- Connect the tail to the head to make a ring, then cut it after the (n − k)-th node — the next node is the new head.
Approach
Walk the list once to find its length n and its tail. Set k %= n; if k is 0, nothing changes. Otherwise link tail.next = head to make a ring, step n − k nodes from the old tail to reach the new tail, then make newHead = newTail.next and set newTail.next = null. k can be 2·10^9, so the modulo is required, not just an optimisation.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next;
Node(long long v) : val(v), next(nullptr) {}
};
int main() {
int n;
cin >> n;
Node dummy(0), *tail = &dummy;
for (int i = 0; i < n; i++) {
long long v;
cin >> v;
tail = tail->next = new Node(v);
}
long long k;
cin >> k;
Node *head = dummy.next;
k %= n;
if (k > 0) {
tail->next = head; // make it a ring
Node *newTail = tail;
for (int i = 0; i < n - k; i++) newTail = newTail->next;
head = newTail->next;
newTail->next = nullptr;
}
for (Node *p = head; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
return 0;
}Python solution
import sys
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
data = sys.stdin.read().split()
n = int(data[0])
k = int(data[n + 1]) % n
head = tail = Node(data[1])
for v in data[2 : n + 1]:
tail.next = Node(v)
tail = tail.next
if k:
tail.next = head # make it a ring
new_tail = tail
for _ in range(n - k):
new_tail = new_tail.next
head = new_tail.next
new_tail.next = None
out = []
while head:
out.append(head.val)
head = head.next
print(" ".join(out))Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node dummy = new Node(0), tail = dummy;
for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
long k = sc.nextLong() % n;
Node head = dummy.next;
if (k > 0) {
tail.next = head; // make it a ring
Node newTail = tail;
for (long i = 0; i < n - k; i++) newTail = newTail.next;
head = newTail.next;
newTail.next = null;
}
StringBuilder sb = new StringBuilder();
for (Node p = head; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
System.out.println(sb);
}
}