当前位置：网站首页>【Leetcode】旋转系列（数组、矩阵、链表、函数、字符串）

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

2022-06-24 18:33:00 【小朱小朱绝不服输】

【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;
        }
    }
}

面试题 01.07. 旋转矩阵

1.题目描述

leetcode链接：面试题 01.07. 旋转矩阵

在这里插入图片描述

2.思路分析

3.参考代码

剑指 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;
    }
}

方法二：递归

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;
    }
}