【Leetcode】旋转系列（数组、矩阵、链表、函数、字符串）

【Leetcode】旋转系列题目总结如下：

旋转系列问题

189. 轮转数组

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

面试题 01.07. 旋转矩阵

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer 24. 反转链表

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

方法二：递归

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
2
3
4
5
6
7
8
9
10
11

61. 旋转链表

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

396. 旋转函数

1.题目描述

leetcode链接：396. 旋转函数

2.思路分析

3.参考代码

796. 旋转字符串

1.题目描述

leetcode链接：796. 旋转字符串

2.思路分析

3.参考代码