Java数据结构与算法 day02 链表

比眉伴天荒 2023-02-11 10:16 31阅读 0赞

### 文章目录 ###

*  第三章 链表
 *   *  单链表介绍和内存布局
     *  单链表创建和遍历的分析实现
     *   *  添加（创建）过程
         *  遍历过程
         *  代码实现
     *  单链表按顺序插入节点
     *  单链表节点的修改
     *  单链表节点的删除和小结
     *  单链表面试题
     *   *  新浪面试题
         *  腾讯面试题
         *  百度面试题
         *  课后练习
     *  双向链表增删改查分析图解及实现
     *  环形链表介绍和约瑟夫问题
     *  约瑟夫问题分析图解和实现
     *  本章导图总结

# 第三章 链表 #

> 本章源码：https://github.com/name365/Java-Data-structure

## 单链表介绍和内存布局 ##

> 链表是有序的列表，但是它**在内存中是实际存储结构**如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center]

小结:
    1.链表是以节点的方式来存储,是链式存储(即各个节点之间并不一定是连续存储的，而是相互指向的);
    2.每个节点包含 data 域:存放数据的域， next 域：指向下一个节点;
    3.如图：发现链表的各个节点不一定是连续存储;
    4.链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定.

> 单链表(带头结点) **逻辑结构**示意图如下:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 1]

## 单链表创建和遍历的分析实现 ##

*  先看一个例子

> 使用带head头的**单向链表**实现 –水浒英雄排行榜管理
> 
> 1)完成对英雄人物的**增删改查**操作， 注: **删除和修改**,**查找可以考虑学员独立完成，也可带学员完成**
> 
> 2)第一种方法在添加英雄时，直接添加到链表的尾部
> 
> 3)**第二种方式在添加英雄时**，根据排名将英雄插入到指定位置  
> (如果有这个排名，则添加失败，并给出提示)

*  单链表的创建示意图(添加), 显示单向链表的分析

class HeroNode { 
        int no;
        String name;
        String nickName;
        HeroNode next;
    }

### 添加（创建）过程 ###

*  先创建一个head 头节点， 作用就是表示单链表的头;

![在这里插入图片描述][20200522230727906.png_pic_center]

*  之后每添加一个节点，就直接加入到—》链表的最后。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 3]

### 遍历过程 ###

*  通过一个辅助变量(临时变量temp)遍历，帮助遍历整个链表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 7]

### 代码实现 ###

/* * 此代码添加数据有问题,待优化 */
    public class SingleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		//测试一下
    		//1.创建节点
    		HeroNode hero = new HeroNode(1,"宋江","及时雨");
    		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    		HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙");
    		HeroNode hero5 = new HeroNode(5,"关胜","大刀");
    		
    		//创建一个链表
    		SingleLinkedList singk = new SingleLinkedList();
    		
    		//添加数据到链表
    		singk.add(hero);
    		singk.add(hero2);
    		singk.add(hero3);
    		singk.add(hero4);
    		singk.add(hero5); 
    		
    		//显示链表
    		singk.list();
    	}
    
    }
    
    //定义一个SingleLinkedList类,来管理我们的英雄
    class SingleLinkedList{ 
    	//先初始化一个头节点,头节点不要动(防止后期找不到此链表),不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    	
    	//添加节点到单向链表
    	//思路，当不考虑编号的顺序时
    	//1.找到当前链表的最后节点
    	//2.将最后这个节点的next域指向这个新的节点
    	public void add(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		//遍历链表,找到最后
    		while(true){ 
    			//找到链表的最后
    			if(temp.next == null){ 	//判定找到了的条件
    				break;
    			}
    			//如果没有找到,将temp后移
    			temp = temp.next;
    		}
    		//当退出循环时,temp就指向了链表的最后
    		//将最后这个节点的next --指向--》 新的节点
    		temp.next = heroNode;
    	}
    	
    	//显示链表[遍历]
    	public void list(){ 
    		//判断链表是否为空
    		if(head.next == null){ 
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		while(true){ 
    			//判断是否到链表的最后
    			if(temp == null){ 
    				break;
    			}
    			//如果不为空，输出节点的信息
    			System.out.println(temp);
    			//注意！！！！将next后移(因为不向后移动,会造成死循环)
    			temp = temp.next;
    		}
    	}
    }
    
    //定义一个HeroNode,每个HeroNode对象就是一个节点
    class HeroNode{ 
    	public int id;
    	public String name;
    	public String nickName;	//别名,昵称
    	public HeroNode next;	//指向下一个节点
    	
    	//构造器
    	public HeroNode(int id, String name, String nickName) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickName = nickName;
    	}
    
    	//为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode [id=" + id + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }

## 单链表按顺序插入节点 ##

*  需要按照编号的顺序添加
 *  首先找到新添加的节点的位置, 是通过辅助变量(指针), **通过遍历来搞定**；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 8]

*  新的节点.next = temp.next

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 9]

*  将temp.next = 新的节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 10]

*  代码实现

/* * 此代码已优化 */
    public class SingleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		//测试一下
    		//1.创建节点
    		HeroNode hero = new HeroNode(1,"宋江","及时雨");
    		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    		HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙");
    		HeroNode hero5 = new HeroNode(5,"关胜","大刀");
    		
    		//创建一个链表
    		SingleLinkedList singk = new SingleLinkedList();
    		
    		//添加数据到链表
    // singk.add(hero);
    // singk.add(hero2);
    // singk.add(hero4);
    // singk.add(hero3);
    // singk.add(hero5); 
    		
    		//添加按照编号的顺序
    		singk.addByOrder(hero);
    		singk.addByOrder(hero4);
    		singk.addByOrder(hero2);
    		singk.addByOrder(hero5); 
    		singk.addByOrder(hero3);
    // singk.addByOrder(hero3);
    		
    		//显示链表
    		singk.list();
    	}
    
    }
    
    //定义一个SingleLinkedList类,来管理我们的英雄
    class SingleLinkedList{ 
    	//先初始化一个头节点,头节点不要动(防止后期找不到此链表),不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    	
    	//第一种方式:第一种方法在添加英雄时，直接添加到链表的尾部
    	//添加节点到单向链表,思路，当不考虑编号的顺序时
    	//1.找到当前链表的最后节点
    	//2.将最后这个节点的next域指向这个新的节点
    	public void add(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		//遍历链表,找到最后
    		while(true){ 
    			//找到链表的最后
    			if(temp.next == null){ 	//判定找到了的条件
    				break;
    			}
    			//如果没有找到,将temp后移
    			temp = temp.next;
    		}
    		//当退出循环时,temp就指向了链表的最后
    		//将最后这个节点的next --指向--》 新的节点
    		temp.next = heroNode;
    	}
    	
    	//显示链表[遍历]
    	public void list(){ 
    		//判断链表是否为空
    		if(head.next == null){ 
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		while(true){ 
    			//判断是否到链表的最后
    			if(temp == null){ 
    				break;
    			}
    			//如果不为空，输出节点的信息
    			System.out.println(temp);
    			//注意！！！！将next后移(因为不向后移动,会造成死循环)
    			temp = temp.next;
    		}
    	}
    	
    	//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    	//(如果有这个排名，则添加失败，并给出提示)
    	public void addByOrder(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp,找到添加的位置
    		//由于是单链表，而找到temp是位于 添加位置的前一个节点,否则插入不了
    		HeroNode temp = head;
    		boolean flag = false;	//标识添加的编号是否存在，默认为false
    		while(true){ 
    			if(temp.next == null){ 	//说明已经在链表的最后
    				break;	
    			}
    			if(temp.next.id > heroNode.id){ 	//位置找到了，就在temp的后面插入
    				break;
    			}else if(temp.next.id == heroNode.id){ 	//说明希望添加的heroNode的编号已然存在
    				flag = true;	//说明编号存在
    				break;
    			}
    			temp = temp.next;	//后移,遍历当前链表
    		}
    		//判断flag的值
    		if(flag){ 	//不能添加,说明编号存在
    			System.out.printf("准备插入的英雄编号%d已经存在了。无法加入\n",heroNode.id);
    		}else{ 
    			//插入到链表中,temp的后面
    			heroNode.next = temp.next;
    			temp.next = heroNode;
    		}
    	}
    
    }
    
    //定义一个HeroNode,每个HeroNode对象就是一个节点
    class HeroNode{ 
    	public int id;
    	public String name;
    	public String nickName;	//别名,昵称
    	public HeroNode next;	//指向下一个节点
    	
    	//构造器
    	public HeroNode(int id, String name, String nickName) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickName = nickName;
    	}
    
    	//为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode [id=" + id + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }

## 单链表节点的修改 ##

## 单链表节点的删除和小结 ##

> 从单链表中删除一个节点的思路图解

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 11]

> 1.  我们先找到 需要删除的这个节点的前一个节点 temp

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 12]

> 1.  temp.next = temp.next.next

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 13]

> 1.  被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

## 单链表面试题 ##

> 单链表的常见面试题有如下:
> 
> 1)求单链表中有效节点的个数
> 
> 2)查找单链表中的倒数第k个结点 【新浪面试题】
> 
> 3)单链表的反转【腾讯面试题，有点难度】
> 
> 4)从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
> 
> 5)合并两个有序的单链表，合并之后的链表依然有序【课后练习.】

*  求单链表中有效节点的个数

public class SingleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		//测试一下
    		//1.创建节点
    		HeroNode hero = new HeroNode(1,"宋江","及时雨");
    		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    		HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙");
    		HeroNode hero5 = new HeroNode(5,"关胜","大刀");
    		
    		//创建一个链表
    		SingleLinkedList singk = new SingleLinkedList();
    		
    		//添加按照编号的顺序
    		singk.addByOrder(hero);
    		singk.addByOrder(hero4);
    		singk.addByOrder(hero2);
    		singk.addByOrder(hero5); 
    		singk.addByOrder(hero3);
    		
    		//显示链表
    		singk.list();
    		
    		//测试一下:求单链表中有效节点的个数
    		System.out.println("单链表有效的节点个数 = " + getLength(singk.getHead()));//5
    	}
    	
    	//获取单链表的节点的个数(如果是带头节点的链表,需求不统计头结点)
    	/** * * @Description * @author subei * @date 2020年5月22日下午5:09:46 * @param head 链表的头节点 * @return 返回的是有效的节点的个数 */
    	public static int getLength(HeroNode head){ 
    		if(head.next == null){ 
    			return 0;
    		}
    		int length = 0;
    		//定义一个临时的变量,未统计头节点
    		HeroNode str = head.next;
    		while(str != null){ 
    			length++;
    			str = str.next;	//即遍历
    		}
    		return length;
    	}
    
    }
    
    //定义一个SingleLinkedList类,来管理我们的英雄
    class SingleLinkedList{ 
    	//先初始化一个头节点,头节点不要动(防止后期找不到此链表),不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    	
    	//返回头节点
    	public HeroNode getHead() { 
    		return head;
    	}
    
    	//第一种方式:第一种方法在添加英雄时，直接添加到链表的尾部
    	//添加节点到单向链表,思路，当不考虑编号的顺序时
    	//1.找到当前链表的最后节点
    	//2.将最后这个节点的next域指向这个新的节点
    	public void add(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		//遍历链表,找到最后
    		while(true){ 
    			//找到链表的最后
    			if(temp.next == null){ 	//判定找到了的条件
    				break;
    			}
    			//如果没有找到,将temp后移
    			temp = temp.next;
    		}
    		//当退出循环时,temp就指向了链表的最后
    		//将最后这个节点的next --指向--》 新的节点
    		temp.next = heroNode;
    	}
    	
    	//修改节点的信息,根据id编号来修改,即id编号不改
    	//说明
    	//1.根据newHeroNode 的 id 来修改即可
    	public void update(HeroNode newHeroNode){ 
    		//判断是否为空
    		if(head.next == null){ 	//链表为空
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//找到需要修改的节点,根据 id 编号
    		//定义一个临时变量
    		HeroNode temp = head.next;
    		boolean flag = false;	//表示是否找到该节点
    		while(true){ 
    			if(temp == null){ 
    				break;	//已经遍历完链表
    			}
    			if(temp.id == newHeroNode.id){ 
    				//找到了
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		//根据flag 判断是否找到要修改的节点
    		if(flag){ 
    			temp.name = newHeroNode.name;
    			temp.nickName = newHeroNode.nickName;
    		}else{ 
    			System.out.printf("没有找到编号为 %d 的节点.\n",newHeroNode.id);
    		}
    	}
    	
    	//删除节点
    	//思路
    	//1.由于头节点head不能动,所以需要一个辅助变量 temp来找到待删除节点的前一个节点
    	//2.说明我们在比较时，是temp.next.id 和 需要删除的节点的id比较
    	public void del(int id){ 
    		HeroNode temp = head;
    		boolean flag = false;	//标志是否找到带删除的节点
    		while(true){ 
    			if(temp.next == null){ 	//已经到链表的最后
    				break;
    			}
    			if(temp.next.id == id){ 	//找到了带删除的节点的前一个节点
    				flag = true;
    				break;
    			}
    			temp = temp.next;	//temp后移，遍历
    		}
    		//判断flag
    		if(flag){ 	//说明找到了
    			//可以删除
    			temp.next = temp.next.next;
    		}else{ 
    			System.out.printf("要删除的节点 %d 不存在。\n",id);
    		}
    	}
    	
    	
    	//显示链表[遍历]
    	public void list(){ 
    		//判断链表是否为空
    		if(head.next == null){ 
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		while(true){ 
    			//判断是否到链表的最后
    			if(temp == null){ 
    				break;
    			}
    			//如果不为空，输出节点的信息
    			System.out.println(temp);
    			//注意！！！！将next后移(因为不向后移动,会造成死循环)
    			temp = temp.next;
    		}
    	}
    	
    	//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    	//(如果有这个排名，则添加失败，并给出提示)
    	public void addByOrder(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp,找到添加的位置
    		//由于是单链表，而找到temp是位于 添加位置的前一个节点,否则插入不了
    		HeroNode temp = head;
    		boolean flag = false;	//标识添加的编号是否存在，默认为false
    		while(true){ 
    			if(temp.next == null){ 	//说明已经在链表的最后
    				break;	
    			}
    			if(temp.next.id > heroNode.id){ 	//位置找到了，就在temp的后面插入
    				break;
    			}else if(temp.next.id == heroNode.id){ 	//说明希望添加的heroNode的编号已然存在
    				flag = true;	//说明编号存在
    				break;
    			}
    			temp = temp.next;	//后移,遍历当前链表
    		}
    		//判断flag的值
    		if(flag){ 	//不能添加,说明编号存在
    			System.out.printf("准备插入的英雄编号%d已经存在了。无法加入\n",heroNode.id);
    		}else{ 
    			//插入到链表中,temp的后面
    			heroNode.next = temp.next;
    			temp.next = heroNode;
    		}
    	}
    
    }
    
    //定义一个HeroNode,每个HeroNode对象就是一个节点
    class HeroNode{ 
    	public int id;
    	public String name;
    	public String nickName;	//别名,昵称
    	public HeroNode next;	//指向下一个节点
    	
    	//构造器
    	public HeroNode(int id, String name, String nickName) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickName = nickName;
    	}
    
    	//为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode [id=" + id + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }

### 新浪面试题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 14]

public class SingleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		//测试一下
    		//1.创建节点
    		HeroNode hero = new HeroNode(1,"宋江","及时雨");
    		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    		HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙");
    		HeroNode hero5 = new HeroNode(5,"关胜","大刀");
    		
    		//创建一个链表
    		SingleLinkedList singk = new SingleLinkedList();
    		
    		//添加按照编号的顺序
    		singk.addByOrder(hero);
    		singk.addByOrder(hero4);
    		singk.addByOrder(hero2);
    		singk.addByOrder(hero5); 
    		singk.addByOrder(hero3);
    		
    		//显示链表
    		singk.list();
    		
    		//测试一下:求单链表中有效节点的个数
    		System.out.println("单链表有效的节点个数 = " + getLength(singk.getHead()));//5
    		
    		//测试一下:查找单链表中的倒数第k个结点 
    		HeroNode res = findLastIndexNode(singk.getHead(), 4);
    		System.out.println("res = "+ res);
    	}
    	
    	//查找单链表中的倒数第k个结点 
    	//思路：
    	//1.编写一个方法,接收head节点,同时接收一个index 
    	//2.index 表示是倒数第index个节点
    	//3.先把链表从头到尾遍历，得到链表的总的长度 getLength
    	//4.得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
    	//5.如果找到了，则返回该节点，否则返回null
    	public static HeroNode findLastIndexNode(HeroNode head, int index) { 
    		//判断如果链表为空，返回null
    		if(head.next == null) { 
    			return null;//没有找到
    		}
    		//第一个遍历得到链表的长度(即节点个数)
    		int size = getLength(head);
    		//第二次遍历 size-index 位置，即倒数的第K个节点
    		//先做一个index的校验
    		if(index <= 0 || index > size) { 
    			return null; 
    		}
    		//第一一个临时变量,for 循环定位到倒数的index
    		HeroNode str = head.next; //3 // 3 - 1 = 2
    		for(int i =0; i< size - index; i++) { 
    			str = str.next;
    		}
    		return str;
    	}
    	
    	//获取单链表的节点的个数(如果是带头节点的链表,需求不统计头结点)
    	/** * * @Description * @author subei * @date 2020年5月22日下午5:09:46 * @param head 链表的头节点 * @return 返回的是有效的节点的个数 */
    	public static int getLength(HeroNode head){ 
    		if(head.next == null){ 
    			return 0;
    		}
    		int length = 0;
    		//定义一个临时的变量,未统计头节点
    		HeroNode str = head.next;
    		while(str != null){ 
    			length++;
    			str = str.next;	//即遍历
    		}
    		return length;
    	}
    
    }
    
    //定义一个SingleLinkedList类,来管理我们的英雄
    class SingleLinkedList{ 
    	//先初始化一个头节点,头节点不要动(防止后期找不到此链表),不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    	
    	//返回头节点
    	public HeroNode getHead() { 
    		return head;
    	}
    	
    	//显示链表[遍历]
    	public void list(){ 
    		//判断链表是否为空
    		if(head.next == null){ 
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		while(true){ 
    			//判断是否到链表的最后
    			if(temp == null){ 
    				break;
    			}
    			//如果不为空，输出节点的信息
    			System.out.println(temp);
    			//注意！！！！将next后移(因为不向后移动,会造成死循环)
    			temp = temp.next;
    		}
    	}
    	
    	//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    	//(如果有这个排名，则添加失败，并给出提示)
    	public void addByOrder(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp,找到添加的位置
    		//由于是单链表，而找到temp是位于 添加位置的前一个节点,否则插入不了
    		HeroNode temp = head;
    		boolean flag = false;	//标识添加的编号是否存在，默认为false
    		while(true){ 
    			if(temp.next == null){ 	//说明已经在链表的最后
    				break;	
    			}
    			if(temp.next.id > heroNode.id){ 	//位置找到了，就在temp的后面插入
    				break;
    			}else if(temp.next.id == heroNode.id){ 	//说明希望添加的heroNode的编号已然存在
    				flag = true;	//说明编号存在
    				break;
    			}
    			temp = temp.next;	//后移,遍历当前链表
    		}
    		//判断flag的值
    		if(flag){ 	//不能添加,说明编号存在
    			System.out.printf("准备插入的英雄编号%d已经存在了。无法加入\n",heroNode.id);
    		}else{ 
    			//插入到链表中,temp的后面
    			heroNode.next = temp.next;
    			temp.next = heroNode;
    		}
    	}
    
    }
    
    //定义一个HeroNode,每个HeroNode对象就是一个节点
    class HeroNode{ 
    	public int id;
    	public String name;
    	public String nickName;	//别名,昵称
    	public HeroNode next;	//指向下一个节点
    	
    	//构造器
    	public HeroNode(int id, String name, String nickName) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickName = nickName;
    	}
    
    	//为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode [id=" + id + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }

### 腾讯面试题 ###

> 单链表的反转,效果图如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 15]

> 思路:
> 
> 1.  先定义一个节点 reverseHead = new HeroNode();
> 2.  从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端.
> 3.  原来的链表的head.next = reverseHead.next
> 
> 具体如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 16]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 17]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 19]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 20]

### 百度面试题 ###

> 从尾到头打印单链表

思路:
    1. 上面的题的要求就是逆序打印单链表.
    2. 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
    3. 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
        
    举例演示栈的使用 Stack

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 21]

*  入栈出栈的代码演示

import java.util.Stack;
    
    //演示栈Stack的基本使用
    public class TestStack { 
    	public static void main(String[] args) { 
    		Stack<String> stack = new Stack();
    		//入栈
    		stack.add("jack");
    		stack.add("Tom");
    		stack.add("smith");
    		
    		//出栈
    		//出栈顺序:smith-->Tom-->jack
    		while(stack.size() > 0){ 
    			System.out.println(stack.pop());	//pop()就是将栈顶的数据取出
    		}
    	}
    }

*  面试题代码实现

import java.util.Stack;
    
    public class SingleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		//测试一下
    		//1.创建节点
    		HeroNode hero = new HeroNode(1,"宋江","及时雨");
    		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    		HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙");
    		HeroNode hero5 = new HeroNode(5,"关胜","大刀");
    		
    		//创建一个链表
    		SingleLinkedList singk = new SingleLinkedList();
    		
    		//添加按照编号的顺序
    		singk.add(hero);
    		singk.add(hero4);
    		singk.add(hero2);
    		singk.add(hero5); 
    		singk.add(hero3);
    
    		System.out.println("原来链表的情况:");
    		singk.list();	//显示链表
    		
    		System.out.println("测试逆序打印的单链表,未改变链表的本身结构:");
    		reversePrint(singk.getHead());	
    	}
    	
    	//方式2：
    	//可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
    	public static void reversePrint(HeroNode head) { 
    		if(head.next == null){ 
    			return;	//空链表，无法打印
    		}
    		//先创建一个栈,将各个节点压入栈中
    		Stack<HeroNode> stack = new Stack<HeroNode>();
    		HeroNode str = head.next;
    		//将链表的所有节点压入栈
    		while(str != null){ 
    			stack.push(str);	
    			str = str.next;	//str后移,这样就可以压入下一个节点
    		}
    		//将栈中的节点进行打印,pop()出栈
    		while(stack.size() > 0){ 
    			System.out.println(stack.pop());	//stack的特点是先进后出
    		}
    	}
    	
    }
    
    //定义一个SingleLinkedList类,来管理我们的英雄
    class SingleLinkedList{ 
    	//先初始化一个头节点,头节点不要动(防止后期找不到此链表),不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    	
    	//返回头节点
    	public HeroNode getHead() { 
    		return head;
    	}
    
    	//第一种方式:第一种方法在添加英雄时，直接添加到链表的尾部
    	//添加节点到单向链表,思路，当不考虑编号的顺序时
    	//1.找到当前链表的最后节点
    	//2.将最后这个节点的next域指向这个新的节点
    	public void add(HeroNode heroNode){ 
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		//遍历链表,找到最后
    		while(true){ 
    			//找到链表的最后
    			if(temp.next == null){ 	//判定找到了的条件
    				break;
    			}
    			//如果没有找到,将temp后移
    			temp = temp.next;
    		}
    		//当退出循环时,temp就指向了链表的最后
    		//将最后这个节点的next --指向--》 新的节点
    		temp.next = heroNode;
    	}
    	
    	//显示链表[遍历]
    	public void list(){ 
    		//判断链表是否为空
    		if(head.next == null){ 
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		while(true){ 
    			//判断是否到链表的最后
    			if(temp == null){ 
    				break;
    			}
    			//如果不为空，输出节点的信息
    			System.out.println(temp);
    			//注意！！！！将next后移(因为不向后移动,会造成死循环)
    			temp = temp.next;
    		}
    	}
    	
    }
    
    //定义一个HeroNode,每个HeroNode对象就是一个节点
    class HeroNode{ 
    	public int id;
    	public String name;
    	public String nickName;	//别名,昵称
    	public HeroNode next;	//指向下一个节点
    	
    	//构造器
    	public HeroNode(int id, String name, String nickName) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickName = nickName;
    	}
    
    	//为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode [id=" + id + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }

### 课后练习 ###

> 合并两个有序的单链表，合并之后的链表依然有序。

public class SingleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		// 测试一下
    		// 1.创建节点
    		HeroNode hero = new HeroNode(1, "宋江", "及时雨");
    		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    		HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
    		HeroNode hero5 = new HeroNode(5, "关胜", "大刀");
    		HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
    		HeroNode hero7 = new HeroNode(7, "秦明", "霹雳火");
    
    		// 创建一个链表
    		SingleLinkedList singk = new SingleLinkedList();
    
    		// 添加按照编号的顺序
    		singk.addByOrder(hero);
    		singk.addByOrder(hero7);
    		singk.addByOrder(hero5);
    
    		// 创建另一个链表
    		SingleLinkedList singk2 = new SingleLinkedList();
    
    		// 添加按照编号的顺序
    		singk2.addByOrder(hero3);
    		singk2.addByOrder(hero6);
    		singk2.addByOrder(hero2);
    		singk2.addByOrder(hero4);
    
    		// 显示链表
    		singk.list();
    		System.out.println("------------------");
    		singk2.list();
    
    		//合并后的
    		System.out.println("合并后的:");
    		SingleLinkedList singk3 = singk.merge(singk, singk2);
            singk3.list();
    	}
    
    }
    
    // 定义一个SingleLinkedList类,来管理我们的英雄
    class SingleLinkedList { 
    	// 先初始化一个头节点,头节点不要动(防止后期找不到此链表),不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    
    	public SingleLinkedList(HeroNode head) { 
    		this.head = head;
    	}
    	
    	public SingleLinkedList() { 
            head = new HeroNode();
        }
    
    	// 显示链表[遍历]
    	public void list() { 
    		// 判断链表是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空！！！");
    			return;
    		}
    		// 由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode temp = head;
    		while (true) { 
    			// 判断是否到链表的最后
    			if (temp == null) { 
    				break;
    			}
    			// 如果不为空，输出节点的信息
    			System.out.println(temp);
    			// 注意！！！！将next后移(因为不向后移动,会造成死循环)
    			temp = temp.next;
    		}
    	}
    
    	// 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    	// (如果有这个排名，则添加失败，并给出提示)
    	public void addByOrder(HeroNode heroNode) { 
    		// 由于头节点head不能动,所以需要一个辅助变量 temp,找到添加的位置
    		// 由于是单链表，而找到temp是位于 添加位置的前一个节点,否则插入不了
    		HeroNode temp = head;
    		boolean flag = false; // 标识添加的编号是否存在，默认为false
    		while (true) { 
    			if (temp.next == null) {  // 说明已经在链表的最后
    				break;
    			}
    			if (temp.next.id > heroNode.id) {  // 位置找到了，就在temp的后面插入
    				break;
    			} else if (temp.next.id == heroNode.id) {  // 说明希望添加的heroNode的编号已然存在
    				flag = true; // 说明编号存在
    				break;
    			}
    			temp = temp.next; // 后移,遍历当前链表
    		}
    		// 判断flag的值
    		if (flag) {  // 不能添加,说明编号存在
    			System.out.printf("准备插入的英雄编号%d已经存在了。无法加入\n", heroNode.id);
    		} else { 
    			// 插入到链表中,temp的后面
    			heroNode.next = temp.next;
    			temp.next = heroNode;
    		}
    	}
    	
    	//合并两个有序的单链表，合并之后的链表依然有序
        public SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) { 
            if (list1.head.next == null) { 
                return list2;
            } else if (list2.head.next == null) { 
                return list1;
            }
    
            HeroNode newNode = new HeroNode();
            HeroNode n1 = newNode;
            HeroNode l1 = list1.head.next;
            HeroNode l2 = list2.head.next;
    
            while (l1 != null && l2 != null) { 
                if (l1.id < l2.id) { 
                    n1.next = l1;
                    l1 = l1.next;
                    n1 = n1.next;
                } else { 
                    n1.next = l2;
                    l2 = l2.next;
                    n1 = n1.next;
                }
            }
    
            if (l1 == null) { 
                n1.next = l2;
            }
            if (l2 == null) { 
                n1.next = l1;
            }
            return new SingleLinkedList(newNode);
        }
    
    }
    
    // 定义一个HeroNode,每个HeroNode对象就是一个节点
    class HeroNode { 
    	public int id;
    	public String name;
    	public String nickName; // 别名,昵称
    	public HeroNode next; // 指向下一个节点
    
    	// 构造器
    	public HeroNode(int id, String name, String nickName) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickName = nickName;
    	}
    
    	public HeroNode() { 
    	}
    
    	// 为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode [id=" + id + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }

## 双向链表增删改查分析图解及实现 ##

> 使用带head头的**双向链表**实现 –水浒英雄排行榜管理单向链表的缺点分析:
> 
> 1)单向链表，**查找的方向只能是一个方向**，而双向链表可以向前或者向后查找。
> 
> 2)单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以**自我删除**，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点.
> 
> 示意图如下:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 22]

> 分析 双向链表的遍历，添加，修改，删除的操作思路：
> 
> 1.  遍历 方式和 单链表一样，只是可以向前查找，也可以向后查找
> 2.  添加 (默认添加到双向链表的最后)
>     
>     (1) 先找到双向链表的最后这个节点
>     
>     (2) temp.next = newHeroNode
>     
>     (3) newHeroNode.pre = temp
> 3.  **修改** 思路和 原来的单向链表的思路一样.
> 4.  **删除**
>     
>     (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
>     
>     (2) 直接找到要删除的这个节点，比如temp
>     
>     (3) temp.pre.next = temp.next
>     
>     (4) temp.next.pre = temp.pre;
> 
> 删除的图示如下:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 23]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 24]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 25]

*  代码实现：

public class DoubleLinkedListTest { 
    
    	public static void main(String[] args) { 
    		// 测试一下
    		// 1.创建节点
    		HeroNode2 hero = new HeroNode2(1, "宋江", "及时雨");
    		HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
    		HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
    		HeroNode2 hero4 = new HeroNode2(4, "公孙胜", "入云龙");
    		HeroNode2 hero5 = new HeroNode2(5, "关胜", "大刀");
    
    		// 创建一个双向链表
    		DoubleLinkedList singk = new DoubleLinkedList();
    
    		// 添加按照编号的顺序
    		singk.add(hero);
    		singk.add(hero4);
    		singk.add(hero2);
    		singk.add(hero5);
    		singk.add(hero3);
    
    		System.out.println("原来链表的情况:");
    		singk.list(); // 显示链表
    
    		// 修改
    		HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "--");
    		singk.update(newHeroNode);
    		System.out.println("修改后的链表情况");
    		singk.list();
    
    		// 删除
    		singk.del(3);
    		System.out.println("删除后的链表情况~~");
    		singk.list();
    	}
    
    }
    
    // 创建一个双向链表的类
    class DoubleLinkedList { 
    	// 先初始化一个头节点, 头节点不要动, 不存放具体的数据
    	private HeroNode2 head = new HeroNode2(0, "", "");
    
    	// 返回头节点
    	public HeroNode2 getHead() { 
    		return head;
    	}
    
    	// 遍历双向链表的方法
    	// 显示链表[遍历]
    	public void list() { 
    		// 判断链表是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空");
    			return;
    		}
    		// 由于头节点head不能动,所以需要一个辅助变量 temp,找到添加的位置
    		HeroNode2 temp = head.next;
    		while (true) { 
    			if (temp == null) {  // 判断是否到链表最后
    				break;
    			}
    			// 输出节点的信息
    			System.out.println(temp);
    			temp = temp.next; // 将temp后移
    		}
    	}
    
    	// 添加一个节点到双向链表的最后.
    	public void add(HeroNode2 heroNode) { 
    		// 由于头节点head不能动,所以需要一个辅助变量 temp
    		HeroNode2 temp = head;
    		// 遍历链表,找到最后
    		while (true) { 
    			// 找到链表的最后
    			if (temp.next == null) {  // 判定找到了的条件
    				break;
    			}
    			// 如果没有找到,将temp后移
    			temp = temp.next;
    		}
    		// 当退出循环时,temp就指向了链表的最后
    		// 将最后这个节点的next --指向--》 新的节点
    		temp.next = heroNode;
    	}
    
    	// 修改节点的信息,根据id编号来修改,即id编号不改
    	// 说明
    	// 1.根据newHeroNode 的 id 来修改即可
    	public void update(HeroNode2 newHeroNode) { 
    		// 判断是否空
    		if(head.next == null){ 	//链表为空
    			System.out.println("链表为空！！！");
    			return;
    		}
    		//找到需要修改的节点,根据 id 编号
    		//定义一个临时变量
    		HeroNode2 temp = head.next;
    		boolean flag = false;	//表示是否找到该节点
    		while(true){ 
    			if(temp == null){ 
    				break;	//已经遍历完链表
    			}
    			if(temp.id == newHeroNode.id){ 
    				//找到了
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		// 根据flag 判断是否找到要修改的节点
    		if (flag) { 
    			temp.name = newHeroNode.name;
    			temp.nickname = newHeroNode.nickname;
    		} else {  // 没有找到
    			System.out.printf("没有找到编号为 %d 的节点，不能修改。\n", newHeroNode.id);
    		}
    	}
    
    	// 删除节点
    	// 思路
    	// 1.由于头节点head不能动,所以需要一个辅助变量 temp来找到待删除节点的前一个节点
    	// 2.说明我们在比较时，是temp.next.id 和 需要删除的节点的id比较
    	public void del(int id) { 
    		HeroNode2 temp = head;
    		boolean flag = false; // 标志是否找到带删除的节点
    		while (true) { 
    			if (temp.next == null) {  // 已经到链表的最后
    				break;
    			}
    			if (temp.next.id == id) {  // 找到了带删除的节点的前一个节点
    				flag = true;
    				break;
    			}
    			temp = temp.next; // temp后移，遍历
    		}
    		// 判断flag
    		if (flag) {  // 说明找到了
    			// 可以删除
    			temp.next = temp.next.next;
    		} else { 
    			System.out.printf("要删除的节点 %d 不存在。\n", id);
    		}
    	}
    }
    
    // 定义HeroNode2 ， 每个HeroNode 对象就是一个节点
    class HeroNode2 { 
    	public String nickName;
    	public int id;
    	public String name;
    	public String nickname;
    	public HeroNode2 next; // 指向下一个节点, 默认为null
    	public HeroNode2 pre; // 指向前一个节点, 默认为null
    
    	// 构造器
    	public HeroNode2(int id, String name, String nickname) { 
    		super();
    		this.id = id;
    		this.name = name;
    		this.nickname = nickname;
    	}
    
    	// 为了显示方便，重写toString方法
    	@Override
    	public String toString() { 
    		return "HeroNode2 [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
    	}
    
    }

## 环形链表介绍和约瑟夫问题 ##

![在这里插入图片描述][20200523170030952.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 26]

>  *  **Josephu** **问题**
> 
> Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
> 
>  *  **提示**
> 
> 用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
> 
>  *  **示意图说明**如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 27]

## 约瑟夫问题分析图解和实现 ##

> **构建**一个单向的环形链表思路
> 
> 1.  先创建第一个节点, 让 first 指向该节点，并形成环形

![在这里插入图片描述][20200523170106126.png_pic_center]

> 1.  后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 28]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 29]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 30]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 31]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 32]

> **遍历**环形链表
> 
> 1.  先让一个辅助指针(变量) curBoy，指向first节点
> 2.  然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 33]

*  代码实现

public class Josepfu { 
    
    	public static void main(String[] args) { 
    		//测试构建环形链表和遍历是否正确
    		CircleLinkList cingk = new CircleLinkList();
    		cingk.addBoy(5);	//加入五个节点
    		cingk.shoeBoy();	//显示一下
    	}
    
    }
    //创建一个单项环形链表
    class CircleLinkList{ 
    	//创建一个first节点,当前没有编号
    	private Boy first = null;
    	//添加新节点,构成一个环形的链表
    	public void addBoy(int nums){ 
    		//nums 进行数据校验
    		if(nums < 1){ 
    			System.out.println("nums的值不正确");
    			return;
    		}
    		Boy curBoy = null;	//辅助变量,帮助构建环形链表
    		//使用循环创建环形链表
    		for(int i = 1;i <= nums;i++){ 
    			//根据编号创建节点
    			Boy boy = new Boy(i);
    			//如果是头节点
    			if(i == 1){ 
    				first = boy;
    				first.setNext(first); //构成环状
    				curBoy = first;	//让curBoy指向第一个节点
    			}else{ 
    				curBoy.setNext(boy);
    				boy.setNext(first);
    				curBoy = boy;
    			}
    		}
    	}
    	
    	//遍历当前环形链表
    	public void shoeBoy(){ 
    		//判断链表是否为空
    		if(first == null){ 
    			System.out.println("链表为空");
    			return;
    		}
    		//因为first头节点不能动,因此创建一个辅助指针完成遍历
    		Boy curBoy = first;
    		while(true){ 
    			System.out.printf("当前节点的编号 %d\n",curBoy.getId());
    			if(curBoy.getNext() == first){ 	//遍历完成
    				break;
    			}
    			curBoy = curBoy.getNext();	//让curBoy后移 
    		}
    	}
    }
    
    //创建一个Boy类,表示一个节点
    class Boy{ 
    	private int id;	//编号
    	private Boy next;	//指向下一个节点,默认为null
    	
    	public Boy(int id){ 
    		this.id = id;
    	}
    
    	public int getId() { 
    		return id;
    	}
    
    	public void setId(int id) { 
    		this.id = id;
    	}
    
    	public Boy getNext() { 
    		return next;
    	}
    
    	public void setNext(Boy next) { 
    		this.next = next;
    	}
    	
    }

> 根据用户的输入，生成一个人物出圈的顺序
> 
> n = 5, 即有5个人
> 
> k = 1, 从第一个人开始报数
> 
> m = 2, 数2下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 34]

> 1.  需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点.
> 
> 补充： 人物报数前，先让 first 和 helper 移动 k - 1次

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 35]

> 1.  当人物报数时，让first 和 helper 指针同时 的移动 m - 1 次

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 36]

> 1.  这时就可以将first 指向的人物节点 出圈
> 
> first = first .next
> 
> helper.next = first
> 
> 原来first 指向的节点就没有任何引用，就会被回收

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 37]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 38]

> 综上，出圈的顺序:2->4->1->5->3

*  代码实现

public class Josepfu { 
    
    	public static void main(String[] args) { 
    		//测试构建环形链表和遍历是否正确
    		CircleLinkList cingk = new CircleLinkList();
    		cingk.addBoy(5);	//加入五个节点
    		cingk.shoeBoy();	//显示一下
    		
    		//测试一下:判断人物出圈是否正确
    		cingk.countBoy(1, 42, 5); // 2->4->1->5->3
    	}
    
    }
    //创建一个单项环形链表
    class CircleLinkList{ 
    	//创建一个first节点,当前没有编号
    	private Boy first = null;
    	//添加新节点,构成一个环形的链表
    	public void addBoy(int nums){ 
    		//nums 进行数据校验
    		if(nums < 1){ 
    			System.out.println("nums的值不正确");
    			return;
    		}
    		Boy curBoy = null;	//辅助变量,帮助构建环形链表
    		//使用循环创建环形链表
    		for(int i = 1;i <= nums;i++){ 
    			//根据编号创建节点
    			Boy boy = new Boy(i);
    			//如果是头节点
    			if(i == 1){ 
    				first = boy;
    				first.setNext(first); //构成环状
    				curBoy = first;	//让curBoy指向第一个节点
    			}else{ 
    				curBoy.setNext(boy);
    				boy.setNext(first);
    				curBoy = boy;
    			}
    		}
    	}
    	
    	//遍历当前环形链表
    	public void shoeBoy(){ 
    		//判断链表是否为空
    		if(first == null){ 
    			System.out.println("链表为空");
    			return;
    		}
    		//因为first头节点不能动,因此创建一个辅助指针完成遍历
    		Boy curBoy = first;
    		while(true){ 
    			System.out.printf("当前节点的编号 %d\n",curBoy.getId());
    			if(curBoy.getNext() == first){ 	//遍历完成
    				break;
    			}
    			curBoy = curBoy.getNext();	//让curBoy后移 
    		}
    	}
    	
    	//根据用户的输入,计算人物出圈的顺序
    	/** * * @Description * @author subei * @date 2020年5月23日下午4:45:48 * @param startId 表示从第几个人物开始数数 * @param countNum 表示数几下 * @param nums 表示最初有几个人物在圈中 */
    	public void countBoy(int startId,int countNum,int nums){ 
    		//先对数据节点进行校验
    		if(first == null || startId < 1 || startId > nums){ 
    			System.out.println("数据有误,请重新输入。");
    			return;
    		}
    		//创建一个辅助指针,帮助人物出圈
    		Boy helper = first;
    		//需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
    		while(true){ 
    			if(helper.getNext() == first){ 	// 说明helper指向最后人物节点
    				break;
    			}
    			helper = helper.getNext();
    		}
    		//人物报数前，先让 first 和 helper 移动 k - 1次
    		for(int j = 0; j < startId - 1; j++) { 
    			first = first.getNext();
    			helper = helper.getNext();
    		}		
    		//当人物报数时，让first 和 helper 指针同时 的移动 m - 1 次
    		//通过循环,知道圈中只有一个节点
    		while(true) { 
    			if(helper == first) {  //说明圈中只有一个人物节点
    				break;
    			}
    			//让 first 和 helper 指针同时 的移动 countNum - 1
    			for(int j = 0; j < countNum - 1; j++) { 
    				first = first.getNext();
    				helper = helper.getNext();
    			}
    			//此处first指向的节点，就是要出圈的人物节点
    			System.out.printf("人物%d出圈\n", first.getId());
    			//此处将first指向的人物节点出圈
    			first = first.getNext();
    			helper.setNext(first);
    		}
    		System.out.printf("最后留在圈中的人物的编号:%d \n", first.getId());
    	}
    }
    
    //创建一个Boy类,表示一个节点
    class Boy{ 
    	private int id;	//编号
    	private Boy next;	//指向下一个节点,默认为null
    	
    	public Boy(int id){ 
    		this.id = id;
    	}
    
    	public int getId() { 
    		return id;
    	}
    
    	public void setId(int id) { 
    		this.id = id;
    	}
    
    	public Boy getNext() { 
    		return next;
    	}
    
    	public void setNext(Boy next) { 
    		this.next = next;
    	}
    	
    }

## 本章导图总结 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 39]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200522230702396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200522230715467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[20200522230727906.png_pic_center]: https://img-blog.csdnimg.cn/20200522230727906.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200522232611865.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200522232630256.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200522232642287.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200522232651441.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/2020052223265843.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20200522232704187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20200522232723529.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20200522232731379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20200522232739526.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20200522232757126.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20200522232806185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 13]: https://img-blog.csdnimg.cn/20200522232813524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 14]: https://img-blog.csdnimg.cn/20200522232840333.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 15]: https://img-blog.csdnimg.cn/20200522232853520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 16]: https://img-blog.csdnimg.cn/20200522232903520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 17]: https://img-blog.csdnimg.cn/20200522232911115.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 18]: https://img-blog.csdnimg.cn/20200522232920446.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 19]: https://img-blog.csdnimg.cn/20200522232928584.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 20]: https://img-blog.csdnimg.cn/2020052223293654.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 21]: https://img-blog.csdnimg.cn/20200522232949953.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 22]: https://img-blog.csdnimg.cn/20200522233006739.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 23]: https://img-blog.csdnimg.cn/20200522233016338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 24]: https://img-blog.csdnimg.cn/20200522233023840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 25]: https://img-blog.csdnimg.cn/20200522233031802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[20200523170030952.png_pic_center]: https://img-blog.csdnimg.cn/20200523170030952.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 26]: https://img-blog.csdnimg.cn/20200523170040568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 27]: https://img-blog.csdnimg.cn/20200523170056935.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[20200523170106126.png_pic_center]: https://img-blog.csdnimg.cn/20200523170106126.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 28]: https://img-blog.csdnimg.cn/20200523170116586.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 29]: https://img-blog.csdnimg.cn/20200523170129669.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 30]: https://img-blog.csdnimg.cn/2020052317013958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 31]: https://img-blog.csdnimg.cn/20200523170146597.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 32]: https://img-blog.csdnimg.cn/20200523170208771.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 33]: https://img-blog.csdnimg.cn/20200523170219688.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 34]: https://img-blog.csdnimg.cn/20200523170229839.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 35]: https://img-blog.csdnimg.cn/20200523170238389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 36]: https://img-blog.csdnimg.cn/20200523170254181.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 37]: https://img-blog.csdnimg.cn/20200523170303873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 38]: https://img-blog.csdnimg.cn/20200523170312926.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 39]: https://img-blog.csdnimg.cn/2020052317054191.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center