【算法集训】Java实现之旋转链表和约瑟夫问题

大家好！我是未来村村长，就是那个“请你跟我这样做，我就跟你这样做！”的村长👨‍🌾！

||Algorithm Day||

​ 未来村村长正推出一系列【Algorithm Day】文章，该系列文章重在提高本人的算法能力，希望能在刷题过程中总结一般方法，提高个人的逻辑思维能力和解题能力。该系列文章以天数为轴，从一个个算法中逐步强化算法相关知识点。

​ ”算法之路，任重而道远。“🌱|day 5|🌾

文章目录

• • ||Algorithm Day||
  • 一、旋转链表
  • • 1、题目描述
    • • （1）描述
      • （2）示例
    • 2、思路分析
    • • （1）实现一思路：循环再断
      • （2）实现二：快慢指针
    • 3、Java实现
    • • （1）实现一：循环再断
      • （2）实现二：快慢指针
  • 二、约瑟夫问题
  • • 1、题目描述
    • • （1）描述
      • （2）示例
    • 2、思路分析
    • • （1）思路一：自建循环链表模拟
      • （2）思路二：使用集合辅助模拟
      • （3）思路三：递推公式
    • 3、Java实现
    • • （1）实现二：利用集合进行模拟
      • （2）实现三：逆推法
  • 三、总结
  • • • （1）取余
      • （2）快慢指针

[声明：以下题目的内容或部分解法来自牛客网或Leetcode，为个人学习总结和记录，也方便大家学习和查阅]

一、旋转链表 1、题目描述 （1）描述

给定链表的头节点，旋转链表，将链表每个节点往右移动 k 个位置，原链表后 k 个位置的节点则依次移动到链表头。

即，例如链表 ： 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3

（2）示例

2、思路分析 （1）实现一思路：循环再断

​ 将单链表的尾节点的next指向头节点，这样就形成了一个循环链表。从头节点开始找到对应位置【因为是整体移动k，则我们只需要将最后剩下的length/k的节点放到前面，对应位置就是length-length/k的节点】进行断链 *** 作，这样就会产生新的头节点，实现整体位移。

（2）实现二：快慢指针

​ 【海康一面的时候没答上来：泪目】

​ 快指针先走k步，然后慢指针与快指针一起走，快指针走到尾部时，慢指针刚好走到旋转链表的尾部。

​ 将慢指针指向的节点的next置为null，将快指针指向的节点的next指向head。

3、Java实现 （1）实现一：循环再断

public class Solution {
    public ListNode rotateLinkedList (ListNode head, int k) {
        //错误判断
        if(head = null) return null;
        //1、求出链表长度
        int length = 1;
        ListNode temp = head;
        while(temp.next!=null){
            temp = temp.next;
            length++;
        }
        //2、链接为循环链表
        temp.next = head;
        //3、找到断链位置
        int newHeadIndex = length - k % length;
        int i = 1;//扫描指针
        ListNode temp2 = head;
        while(i<newHeadIndex){
            temp2 = temp2.next;
            i++;
        }
        //4、将断链位置的下一个节点作为头节点，并返回
        ListNode newHead = temp2.next;
        temp2.next = null;
        return newHead;
    }
}

​ 技巧一：链表和数组不同，一般我们要计算链表长度或定位链表位置，初始指针我们置为1而不是0。

​ 技巧二：取余% *** 作，我们在用数组创建循环队列时会使用到，是一个查找相应位置【等距离】的常用方法

（2）实现二：快慢指针

public class Solution {
    public ListNode rotateLinkedList (ListNode head, int k) {
        //错误判断一
        if(head = null || k==0) return head;
        //快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //链表长度
        int length = 1;
        ListNode temp = head;
        while(temp.next!=null){
            temp = temp.next;
            length++;
        }
        //快指针先走k步，走到k%length==0的位置
        while((k%length)!=0){
      		fast = fast.next;
            k--;
        }
        //一起走
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newhead = slow.next;
        fast.next = head;
        slow.next = null;
        
        return newhead;
    }
} 

​ 这里最关键的处理是让快指针先走k步，然而k的大小可能大于链表的长度，这样就会发生越界问题。我们使用k%length来进行判断。如果k小于链表长度，则fast指针正常走到k，直到0/length==0；如果k大于链表长度，我们可以过滤掉重复走过的路程，我们只需要走k%length的余数即可。

二、约瑟夫问题 1、题目描述 （1）描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人被杀死。下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

经典故事：

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

（2）示例

2、思路分析 （1）思路一：自建循环链表模拟

​ 建立一个循环链表，完全对题目描述进行还原模拟。

​ 还原模拟的原理比较简单：

• 我们只需要建立一个循环链表，然后遍历链表；
• 每次遍历都设定index=1，遍历一个节点则使index++；
• 当index==m-1时，使temp.next=temp.next.next，即把第m个节点撤销
• 重复直到temp.nxet==temp，即只剩一个节点，返回相应的值即可

（2）思路二：使用集合辅助模拟

​ 使用ArrayList进行模拟，然后每次都将index=(index+m-1)%n的元素拿出，直到只剩下最后一个元素。

​ 这里的问题的关键就在于为什么每次都拿走index=(index+m-1)%n的元素？

​ 我们假设m=2，n=5。最开始index=1，那第一个走的人就是(1+m-1)%n，即除了重复循环以外的第m个人。等到了第二个人，m也变了，n也变了，而且是从第二个人开始报数【因为第二个人被杀死了，所以第三个人变成第二个人了】。

​ 因为每次都是从被杀死的下一个开始，所以踢走的人就是从index开始到喊到m的人。

（3）思路三：递推公式

​ 我们直接来看代码，代码十分简单就三行，具体执行就一个for循环

int index= 0;
for(int i=2;i<=n;i++)  index=(index+m)%i;
return index+1; 

​ 太抽象了，我们画个图来理解一下，就用n=5，m=2来试试。

​ 我们先来试试for循环：

​ 很懵逼得出的res结果序列是：00202，最后是2，加1进行返回

​ 没关系我们再来看一张图：

​ 还是看不懂？我来解释一下图二，然后解释图一，就差不多了。

• 图二：

  • 因为我们每杀一个人，下一次报数就从被杀的下一位开始，那我们就把这个报数的人看作这个循环链表【因为实际上是一个循环链表】的头节点，即其index为0。如图第三个人的index依次为：20200，是不是正好和00202相反，其实公式就是一个倒推的过程；
  • 如果我们知道谁最后一个活下来，那我们能不能根据最后一个人所在的index，推出其上一轮的index，一直往上推，推到没有人死的时候，其对应的index+1就是这个人的编号

• 图一：是图二的想法实现

  • 再看公式：for(int i=2;i<=n;i++) index=(index+m)%i
    • 首先i是啥意思？是倒数第i轮的人数i。
    • index是啥？左边的index是上一轮最后一个人【称为Winer】所在的位置，右边的index这轮Winner所在的位置
  • 我们看[5,1,3]到[3,4,5,1]，即对应index=(2+2)%4=0
    • 还记得上一题的旋转链表吗，我们将[3,4,5,1]的元素整体向后移动2位，是不是得到[5,1,3,4]，是不是一个道理？
    • 既然如此，我们将[5,1,3]整体向前移动2位，是不是得到[3,5,1]。因为每次都有两个人报数，然后第三个人成为头节点，就相当于整体向后移动了2位，如果要还原，就得将该元素整体向前移动两位。因为是变化的循环链表，所以我们就在这个变化的循环链表中进行整体移动。

3、Java实现 （1）实现二：利用集合进行模拟

public class Solution {
    public static int ysf(int n, int m) {
        //创建一个List，用于模拟
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i<n;i++) list.add(i);       
        //进行模拟
        int index = 0;//将被杀掉的人的下标
        whlie(list.size>1){
            index = (index + m - 1) % list.size();
            list.remove(index);
        }
        return list.remove(0) + 1;
    }
}

（2）实现三：逆推法

public class Solution {
    public int ysf(int n, int m) {
        int index = 0;
        for(int i = 2;i<=n;i++) index = (index + m)%i;
        return index+1;
    }
}

三、总结 （1）取余

​ 今天的题目都涉及到了取余，我们发现

• 旋转链表中有一个固定移动距离K值，然后约瑟夫问题中有一个固定报数被杀的值m。
• 旋转链表中可视为循环链表，约瑟夫问题也可以视作不断变化的循环链表

​ 我们可以得出结论，固定移动值+循环→考虑使用取余实现定位。

（2）快慢指针

​ 在单向链表问题中，我们不能使用前后两个指针来进行遍历寻找，但是可以使用两个速度不同的指针进行遍历寻找，控制两者的速度【间距】来实现一些特定的遍历问题【比如判断一个链表是否出现回环】。