【Leetcode】旋转系列题目总结如下:
1.题目描述
leetcode链接:189. 轮转数组


2.思路分析
根据k来轮转数组,要求空间复杂度为O(1),因此需要在原数组上进行反转,因此可以先反转整个数组,再把前k个反转,再把后n-k个反转。
需要注意的是:k大于nums.length的情况,需要用k对nums.length取模。
3.参考代码
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int tmp = nums[start];
nums[start++] = nums[end];
nums[end--] = tmp;
}
}
}
1.题目描述
leetcode链接:面试题 01.07. 旋转矩阵

2.思路分析
每次交换菱形四个顶点。
3.参考代码
class Solution {
public void rotate(int[][] matrix) {
// 交换菱形四个顶点
int n = matrix.length;
int start = 0, end = n - 1;
while (start < end) {
for (int i = 0; i < end - start; i++) {
int tmp = matrix[start][start + i];
matrix[start][start + i] = matrix[end - i][start];
matrix[end - i][start] = matrix[end][end - i];
matrix[end][end - i] = matrix[start + i][end];
matrix[start + i][end] = tmp;
}
start++;
end--;
}
}
}
1.题目描述
leetcode链接:剑指 Offer 24. 反转链表

2.思路分析
方法一:迭代法(双指针)

方法二:递归
使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点的 next 引用指向。
3.参考代码
方法一:迭代法(双指针)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dumpy = null;
while (head != null) {
ListNode tmp = head.next;
head.next = dumpy;
dumpy = head;
head = tmp;
}
return dumpy;
}
}
方法二:递归
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
}
1.题目描述
leetcode链接:61. 旋转链表

2.思路分析
先统计链表长度,同时将链表首尾相连,然后对k进行取模,判断旋转点。然后旋转点以后的点赋值为新节点,再把旋转点之后的点赋值为null即可。
3.参考代码
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
ListNode p = head;
int n = 1; // 统计链表长度
while (p.next != null) {
n++;
p = p.next;
}
k %= n;
if (k == 0) return head;
p.next = head; // 首尾相连
// 找到旋转点
for (int i = 0; i < n - k; i++) {
p = p.next;
}
ListNode newHead = p.next; // 将旋转点后面的点赋值给新的头节点
p.next = null; // 将该旋转点点之后赋为null
return newHead;
}
}
1.题目描述
leetcode链接:396. 旋转函数

2.思路分析
3.参考代码
1.题目描述
leetcode链接:796. 旋转字符串

2.思路分析
3.参考代码