Java数据结构与算法_02 链表（约瑟夫问题）

水深无声 2023-07-08 05:50 21阅读 0赞

### Java数据结构与算法\_02 ###

*  单向链表
 *   *  添加数据（创建）
     *  修改节点信息
     *  删除节点信息
     *  完整代码
 *  面试题
 *   *  完整代码
 *  双向链表
 *   *  完整代码
 *  单向环形链表（约瑟夫问题）
 *   *  完整代码

--------------------

***本人是个新手，写下博客用于自我复习、自我总结。  
如有错误之处，请各位大佬指出。  
学习资料来源于：尚硅谷***

--------------------

# 单向链表 #

链表是有序的列表，但是它在内存中是存储如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70]  
链表是以节点的方式来存储的，每个节点包含 data 域， next 域，data用来存放数据，next用来指向下一个节点。正因为这种特性，链表的各个节点不一定是连续存储。链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

单链表(带头结点) 逻辑结构示意图如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70 1]  
头结点实际上不存放具体的数据，作用就是表示单链表。

## 添加数据（创建） ##

添加数据有两种情况，  
第一种是：创建一个head 头节点， 之后每添加一个节点，就直接加入到链表的最后。  
第二种是：创建一个head 头节点， 之后按照一些顺序（比如编号）把节点添加到链表的相应位置上。

第一种的思路是：  
1.首先找到当前链表的最后节点。这就需要遍历寻找最后节点。显然，这就需要从头节点开始遍历，但是由于头节点本身不能动，所以就可以通过一个辅助变量，来帮助遍历整个链表。  
2.找到了最后的节点之后，只要将最后这个节点的next 指向 新的节点 即可。

第二种的思路是：  
1.首先找到新添加的节点的位置。通过辅助变量temp的遍历来完成。需要注意的是，这个 temp 需要位于 添加位置的前一个节点，否则插入不了。（因为是单向链表）  
2.找到位置之后，新的节点的next 只要指向 temp.next ，再将temp.next 指向 新的节点 即可。

// 添加节点到单向链表，不考虑编号顺序时
    	public void add(Node newNode) { 
    		// 因为head节点不能动，因此我们需要辅助变量temp来遍历
    		Node temp = head;
    		// 遍历链表，找到最后
    		while (true) { 
    			// 如果找到了链表的最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 如果没有找到最后, 将将temp后移
    			temp = temp.next;
    		}
    		// 当退出while循环时，temp就指向了链表的最后
    		// 将最后这个节点的next 指向 新的节点
    		temp.next = newNode;
    	}
    
    	// 添加节点到单向链表，考虑编号顺序时
    	// (如果对应编号上，有数据，则添加失败)
    	public void addByOrder(Node newNode) { 
    		// 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置
    		// 这个 temp 需要位于 添加位置的前一个节点，否则插入不了
    		Node temp = head;
    		boolean flag = false; // 判断添加的编号是否存在，默认为false
    		while (true) { 
    			// 当temp已经在链表的最后，退出即可。因为新节点肯定在最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 位置找到，就在temp的后面插入
    			if (temp.next.no > newNode.no) { 
    				break;
    			}
    			// 说明希望添加的节点的编号已经存在
    			else if (temp.next.no == newNode.no) { 
    				flag = true; // 说明编号存在
    				break;
    			}
    			temp = temp.next; // 后移，遍历当前链表
    		}
    		// 判断flag的值
    		// 不能添加，说明编号存在
    		if (flag) { 
    			System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no);
    		}
    		// 可以插入
    		else { 
    			// 插入到链表中, temp的后面
    			newNode.next = temp.next;
    			temp.next = newNode;
    		}
    	}

## 修改节点信息 ##

即然想修改节点信息，肯定就要想怎么找到想修改的节点。肯定还是用辅助变量temp来遍历。所以在设计节点的时候，除了data和next，还可以设计一个no编号，或者设计其他的一些用来判断的。

// 修改节点的信息, 根据no编号来修改
    	public void update(Node newNode) { 
    		// 判断是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空~");
    			return;
    		}
    		// 找到需要修改的节点, 根据no编号
    		// 定义一个辅助变量
    		Node temp = head.next;
    		boolean flag = false; // 表示是否找到该节点
    		while (true) { 
    			if (temp == null) { 
    				break; // 已经遍历完链表
    			}
    			if (temp.no == newNode.no) { 
    				// 找到
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		// 根据flag 判断是否找到要修改的节点
    		if (flag) { 
    			temp.data = newNode.data;
    		} 
    		// 没有找到
    		else {  
    			System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
    		}
    	}

## 删除节点信息 ##

首先找到需要删除的这个节点的前一个节点 temp，依然使用辅助变量。确定到这个位置，只需要让temp.next.no 和 需要删除的节点的no比较。确定好位置后，让temp.next 指向 temp.next.next即可。被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。

// 删除节点
    	public void del(int no) { 
    		Node temp = head;
    		boolean flag = false; // 标志是否找到待删除节点的
    		while (true) { 
    			// 已经到链表的最后
    			if (temp.next == null) {  
    				break;
    			}
    			if (temp.next.no == no) { 
    				// 找到的待删除节点的前一个节点temp
    				flag = true;
    				break;
    			}
    			temp = temp.next; // temp后移
    		}
    		// 判断flag
    		if (flag) {  // 找到
    			// 可以删除
    			temp.next = temp.next.next;
    		} else { 
    			System.out.printf("要删除的 %d 节点不存在\n", no);
    		}
    	}

## 完整代码 ##

public class SingleLinkedListDemo { 
    
    	public static void main(String[] args) { 
    		// 先创建节点
    		Node hero1 = new Node(1, "宋江");
    		Node hero2 = new Node(2, "卢俊义");
    		Node hero3 = new Node(3, "吴用");
    		Node hero4 = new Node(4, "林冲");
    
    		// 创建一个链表
    		SingleLinkedList singleLinkedList = new SingleLinkedList();
    
    		// 加入
    		singleLinkedList.add(hero1);
    		singleLinkedList.add(hero4);
    		singleLinkedList.add(hero2);
    		singleLinkedList.add(hero3);
    
    		/* 按照编号的顺序加入 * singleLinkedList.addByOrder(hero1); * singleLinkedList.addByOrder(hero4); * singleLinkedList.addByOrder(hero2); * singleLinkedList.addByOrder(hero3); * */
    		
    		/* 修改节点 * HeroNode newNode = new Node(2, "小卢"); * singleLinkedList.update(newNode); * */
    		
    		/* 删除节点 * singleLinkedList.del(1); */
    	 
    		System.out.println("链表：");
    		singleLinkedList.list();
    
    	}
    }
    
    // 定义SingleLinkedList 对数据进行操作
    class SingleLinkedList { 
    
    	// 先初始化一个头节点, 头节点不能动, 不存放具体的数据
    	private Node head = new Node(0, "");
    
    	// 返回头节点
    	public Node getHead() { 
    		return head;
    	}
    
    	// 添加节点到单向链表，不考虑编号顺序时
    	public void add(Node newNode) { 
    		// 因为head节点不能动，因此我们需要辅助变量temp来遍历
    		Node temp = head;
    		// 遍历链表，找到最后
    		while (true) { 
    			// 如果找到了链表的最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 如果没有找到最后, 将将temp后移
    			temp = temp.next;
    		}
    		// 当退出while循环时，temp就指向了链表的最后
    		// 将最后这个节点的next 指向 新的节点
    		temp.next = newNode;
    	}
    
    	// 添加节点到单向链表，考虑编号顺序时
    	// (如果对应编号上，有数据，则添加失败)
    	public void addByOrder(Node newNode) { 
    		// 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置
    		// 这个 temp 需要位于 添加位置的前一个节点，否则插入不了
    		Node temp = head;
    		boolean flag = false; // 判断添加的编号是否存在，默认为false
    		while (true) { 
    			// 当temp已经在链表的最后，退出即可。因为新节点肯定在最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 位置找到，就在temp的后面插入
    			if (temp.next.no > newNode.no) { 
    				break;
    			}
    			// 说明希望添加的节点的编号已经存在
    			else if (temp.next.no == newNode.no) { 
    				flag = true; // 说明编号存在
    				break;
    			}
    			temp = temp.next; // 后移，遍历当前链表
    		}
    		// 判断flag的值
    		// 不能添加，说明编号存在
    		if (flag) { 
    			System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no);
    		}
    		// 可以插入
    		else { 
    			// 插入到链表中, temp的后面
    			newNode.next = temp.next;
    			temp.next = newNode;
    		}
    	}
    
    	// 修改节点的信息, 根据no编号来修改
    	public void update(Node newNode) { 
    		// 判断是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空~");
    			return;
    		}
    		// 找到需要修改的节点, 根据no编号
    		// 定义一个辅助变量
    		Node temp = head.next;
    		boolean flag = false; // 表示是否找到该节点
    		while (true) { 
    			if (temp == null) { 
    				break; // 已经遍历完链表
    			}
    			if (temp.no == newNode.no) { 
    				// 找到
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		// 根据flag 判断是否找到要修改的节点
    		if (flag) { 
    			temp.data = newNode.data;
    		} 
    		// 没有找到
    		else {  
    			System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
    		}
    	}
    
    	// 删除节点
    	public void del(int no) { 
    		Node temp = head;
    		boolean flag = false; // 标志是否找到待删除节点的
    		while (true) { 
    			// 已经到链表的最后
    			if (temp.next == null) {  
    				break;
    			}
    			if (temp.next.no == no) { 
    				// 找到的待删除节点的前一个节点temp
    				flag = true;
    				break;
    			}
    			temp = temp.next; // temp后移
    		}
    		// 判断flag
    		if (flag) {  // 找到
    			// 可以删除
    			temp.next = temp.next.next;
    		} else { 
    			System.out.printf("要删除的 %d 节点不存在\n", no);
    		}
    	}
    
    	// 显示链表[遍历]
    	public void list() { 
    		// 判断链表是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空");
    			return;
    		}
    		// 因为头节点不能动，因此我们需要一个辅助变量来遍历
    		Node temp = head.next;
    		while (true) { 
    			// 判断是否到链表最后
    			if (temp == null) { 
    				break;
    			}
    			// 输出节点的信息
    			System.out.println(temp);
    			// 将temp后移， 一定小心
    			temp = temp.next;
    		}
    	}
    }
    
    // 定义Node ， 每个Node对象就是一个节点
    class Node { 
    	public int no;
    	public String data;
    	public Node next; // 指向下一个节点
    
    	// 构造器
    	public Node(int no, String data) { 
    		this.no = no;
    		this.data = data;
    	}
    
    	@Override
    	public String toString() { 
    		return "Node [no=" + no + "，data=" + data + "]";
    	}
    
    }

--------------------

# 面试题 #

![在这里插入图片描述][20200225131842155.png]  
***分析：***

**第一题**很简单，只需要找一个辅助变量，像之前一样遍历即可，再加一个变量用来计数。只要辅助变量的next为null就停止。只需要注意头节点应不应该计算在内。

**第二题：**

1.编写一个方法，接收head节点，同时接收一个index。这个index 表示的是倒数第index个节点。

2.先把链表从头到尾遍历，得到链表的总的长度 size。利用第一题就可以得到。依然不包括头节点。

3.判断index是否满足条件：index <= 0 || index > size 。满足这个条件，显然不符合标准，返回null即可。

4.满足了条件之后，我们依然利用辅助变量，从链表的头节点后的第一个节点开始遍历，遍历 size-index 次，就可以得到该节点。

（假如链表不包括头节点，有5个节点，倒数第4个节点，就是正数第2个节点，即从第一个节点开始遍历，遍历5-4=1次，让辅助变量遍历到第2个节点并返回即可）

（当然遍历的条件和方式有很多种，可以自行变换）

5.如果找到了，则返回该节点，否则返回null

**第三题：**

1.首先，如果当前链表为空，或者只有一个节点，无需反转，直接返回。

2.定义一个新的头节点 reverseHead，用来记录反转后的链表。

3.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端。

4.最后，让原来的链表的head.next = reverseHead.next，就完成了转换。

**第四题：**

逆序打印单链表有两种方式，

方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，就像第三题那样。

方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果。

对于方式2，就很简单了，只要知道栈的基本用法就可以实现：  
（现在先简单说明）

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");
    
    		// 出栈
    		while (stack.size() > 0) { 
    			System.out.println(stack.pop());//pop就是将栈顶的数据取出
    		}
    	}
    
    }

--------------------

## 完整代码 ##

import java.util.Stack;
    
    public class SingleLinkedListDemo { 
    
    	public static void main(String[] args) { 
    		// 先创建节点
    		Node hero1 = new Node(1, "宋江");
    		Node hero2 = new Node(2, "卢俊义");
    		Node hero3 = new Node(3, "吴用");
    		Node hero4 = new Node(4, "林冲");
    
    		// 创建一个链表
    		SingleLinkedList singleLinkedList = new SingleLinkedList();
    
    		// 加入
    		singleLinkedList.add(hero1);
    		singleLinkedList.add(hero4);
    		singleLinkedList.add(hero2);
    		singleLinkedList.add(hero3);
    
    		/* * 按照编号的顺序加入 singleLinkedList.addByOrder(hero1); * singleLinkedList.addByOrder(hero4); * singleLinkedList.addByOrder(hero2); * singleLinkedList.addByOrder(hero3); */
    
    		/* * 修改节点 HeroNode newNode = new Node(2, "小卢"); * singleLinkedList.update(newNode); */
    
    		/* * 删除节点 singleLinkedList.del(1); */
    
    		System.out.println("原来链表的情况：");
    		singleLinkedList.list();
    
    		/* * 求单链表中有效节点的个数 * System.out.println("有效的节点个数=" +getLength(singleLinkedList.getHead())); * * 得到倒数第K个节点 * Node res = findLastIndexNode(singleLinkedList.getHead(),3); * System.out.println("res=" + res); */
    
    		// System.out.println("反转单链表：");
    		// reverseList(singleLinkedList.getHead());
    		// singleLinkedList.list();
    
    		System.out.println("逆序打印单链表, 没有改变链表的结构：");
    		reversePrint(singleLinkedList.getHead());
    
    	}
    
    	// 题目一：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
    	public static int getLength(Node head) { 
    		if (head.next == null) {  // 空链表
    			return 0;
    		}
    		int length = 0;
    		// 定义一个辅助的变量，不计算头节点
    		Node cur = head.next;
    		while (cur != null) { 
    			length++;
    			cur = cur.next; // 遍历
    		}
    		return length;
    	}
    
    	// 题目二：查找单链表中的倒数第k个结点 
    	public static Node findLastIndexNode(Node head, int index) { 
    		// 如果链表为空，返回null
    		if (head.next == null) { 
    			return null;
    		}
    		// 第一个遍历得到链表的长度(节点个数)
    		int size = getLength(head);
    		// 先做一个index的校验
    		if (index <= 0 || index > size) { 
    			return null;
    		}
    		// 第二次遍历到 size-index 位置，就是倒数的第K个节点
    		// 定义辅助变量， 定位到倒数的index
    		Node cur = head.next; 
    		for (int i = 0; i < size - index; i++) { 
    			cur = cur.next;
    		}
    		return cur;
    	}
    
    	// 题目三：将单链表反转
    	public static void reverseList(Node head) { 
    		// 如果当前链表为空，或者只有一个节点，无需反转，直接返回
    		if (head.next == null || head.next.next == null) { 
    			return;
    		}
    	
    		// 定义一个辅助变量，帮助遍历原来的链表
    		Node cur = head.next;
    		Node next = null;// 指向当前节点[cur]的下一个节点
    		Node reverseHead = new Node(0, "");
    		// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
    		while (cur != null) { 
    			next = cur.next;// 先暂时保存当前节点的下一个节点，因为后面需要使用
    			cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的最前端
    			reverseHead.next = cur; // 将cur 连接到新的链表上
    			cur = next;// 让cur后移
    		}
    		// 将head.next 指向 reverseHead.next , 实现单链表的反转
    		head.next = reverseHead.next;
    	}
    
    	// 题目四的方式2：
    	// 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
    	public static void reversePrint(Node head) { 
    		if (head.next == null) { 
    			return;// 空链表，不能打印
    		}
    		// 创建一个栈，将各个节点压入栈
    		Stack<Node> stack = new Stack<Node>();
    		Node cur = head.next;
    		// 将链表的所有节点压入栈
    		while (cur != null) { 
    			stack.push(cur);
    			cur = cur.next; // cur后移，这样就可以压入下一个节点
    		}
    		// 将栈中的节点进行打印,pop 出栈
    		while (stack.size() > 0) { 
    			System.out.println(stack.pop()); // stack的特点是先进后出
    		}
    	}
    
    }
    
    // 定义SingleLinkedList 对数据进行操作
    class SingleLinkedList { 
    
    	// 先初始化一个头节点, 头节点不能动, 不存放具体的数据
    	private Node head = new Node(0, "");
    
    	// 返回头节点
    	public Node getHead() { 
    		return head;
    	}
    
    	// 添加节点到单向链表，不考虑编号顺序时
    	public void add(Node newNode) { 
    		// 因为head节点不能动，因此我们需要辅助变量temp来遍历
    		Node temp = head;
    		// 遍历链表，找到最后
    		while (true) { 
    			// 如果找到了链表的最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 如果没有找到最后, 将将temp后移
    			temp = temp.next;
    		}
    		// 当退出while循环时，temp就指向了链表的最后
    		// 将最后这个节点的next 指向 新的节点
    		temp.next = newNode;
    	}
    
    	// 添加节点到单向链表，考虑编号顺序时
    	// (如果对应编号上，有数据，则添加失败)
    	public void addByOrder(Node newNode) { 
    		// 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置
    		// 这个 temp 需要位于 添加位置的前一个节点，否则插入不了
    		Node temp = head;
    		boolean flag = false; // 判断添加的编号是否存在，默认为false
    		while (true) { 
    			// 当temp已经在链表的最后，退出即可。因为新节点肯定在最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 位置找到，就在temp的后面插入
    			if (temp.next.no > newNode.no) { 
    				break;
    			}
    			// 说明希望添加的节点的编号已经存在
    			else if (temp.next.no == newNode.no) { 
    				flag = true; // 说明编号存在
    				break;
    			}
    			temp = temp.next; // 后移，遍历当前链表
    		}
    		// 判断flag的值
    		// 不能添加，说明编号存在
    		if (flag) { 
    			System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no);
    		}
    		// 可以插入
    		else { 
    			// 插入到链表中, temp的后面
    			newNode.next = temp.next;
    			temp.next = newNode;
    		}
    	}
    
    	// 修改节点的信息, 根据no编号来修改
    	public void update(Node newNode) { 
    		// 判断是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空~");
    			return;
    		}
    		// 找到需要修改的节点, 根据no编号
    		// 定义一个辅助变量
    		Node temp = head.next;
    		boolean flag = false; // 表示是否找到该节点
    		while (true) { 
    			if (temp == null) { 
    				break; // 已经遍历完链表
    			}
    			if (temp.no == newNode.no) { 
    				// 找到
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		// 根据flag 判断是否找到要修改的节点
    		if (flag) { 
    			temp.data = newNode.data;
    		}
    		// 没有找到
    		else { 
    			System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
    		}
    	}
    
    	// 删除节点
    	public void del(int no) { 
    		Node temp = head;
    		boolean flag = false; // 标志是否找到待删除节点的
    		while (true) { 
    			// 已经到链表的最后
    			if (temp.next == null) { 
    				break;
    			}
    			if (temp.next.no == no) { 
    				// 找到的待删除节点的前一个节点temp
    				flag = true;
    				break;
    			}
    			temp = temp.next; // temp后移
    		}
    		// 判断flag
    		if (flag) {  // 找到
    			// 可以删除
    			temp.next = temp.next.next;
    		} else { 
    			System.out.printf("要删除的 %d 节点不存在\n", no);
    		}
    	}
    
    	// 显示链表[遍历]
    	public void list() { 
    		// 判断链表是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空");
    			return;
    		}
    		// 因为头节点不能动，因此我们需要一个辅助变量来遍历
    		Node temp = head.next;
    		while (true) { 
    			// 判断是否到链表最后
    			if (temp == null) { 
    				break;
    			}
    			// 输出节点的信息
    			System.out.println(temp);
    			// 将temp后移， 一定小心
    			temp = temp.next;
    		}
    	}
    }
    
    // 定义Node ， 每个Node对象就是一个节点
    class Node { 
    	public int no;
    	public String data;
    	public Node next; // 指向下一个节点
    
    	// 构造器
    	public Node(int no, String data) { 
    		this.no = no;
    		this.data = data;
    	}
    
    	@Override
    	public String toString() { 
    		return "Node [no=" + no + "，data=" + data + "]";
    	}
    
    }

--------------------

# 双向链表 #

单向链表有一些缺点：

（1）单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找；

（2）单向链表不能自我删除，需要靠辅助节点。而双向链表，则可以自我删除。这也就是为什么之前单链表删除节点时，总是需要先找到待删除节点的前一个节点。

也就是说，双向链表是对单向链表的改进，不仅可以记录数据和下一个节点，现在又可以记录上一个节点。

对双向链表的操作和对单向链表的操作，没有太大的不同，就是注意需要指向上一个节点即可。

## 完整代码 ##

public class DoubleLinkedListDemo { 
    
    	public static void main(String[] args) { 
    
    		// 创建节点
    		Node2 hero1 = new Node2(1, "宋江");
    		Node2 hero2 = new Node2(2, "卢俊义");
    		Node2 hero3 = new Node2(3, "吴用");
    		Node2 hero4 = new Node2(4, "林冲");
    		// 创建一个双向链表
    		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
    		doubleLinkedList.addByOrder(hero4);
    		doubleLinkedList.addByOrder(hero2);
    		doubleLinkedList.addByOrder(hero3);
    		doubleLinkedList.addByOrder(hero1);
    
    		System.out.println("原来链表的情况：");
    		doubleLinkedList.list();
    
    		// 修改
    		Node2 newNode = new Node2(4, "公孙胜");
    		doubleLinkedList.update(newNode);
    		System.out.println("修改后的链表情况");
    		doubleLinkedList.list();
    
    		// 删除
    		doubleLinkedList.del(3);
    		System.out.println("删除后的链表情况");
    		doubleLinkedList.list();
    	}
    
    }
    
    // 创建一个双向链表的类
    class DoubleLinkedList { 
    
    	// 先初始化一个头节点, 头节点不要动, 不存放具体的数据
    	private Node2 head = new Node2(0, "");
    
    	// 返回头节点
    	public Node2 getHead() { 
    		return head;
    	}
    
    	// 遍历双向链表的方法
    	// 显示链表[遍历]
    	public void list() { 
    		// 判断链表是否为空
    		if (head.next == null) { 
    			System.out.println("链表为空");
    			return;
    		}
    		// 因为头节点不能动，因此我们需要一个辅助变量来遍历
    		Node2 temp = head.next;
    		while (true) { 
    			// 判断是否到链表最后
    			if (temp == null) { 
    				break;
    			}
    			// 输出节点的信息
    			System.out.println(temp);
    			// 将temp后移， 一定小心
    			temp = temp.next;
    		}
    	}
    
    	// 添加一个节点到双向链表的最后
    	public void add(Node2 newNode) { 
    		// 因为头节点不能动，因此我们需要一个辅助变量来遍历
    		Node2 temp = head;
    		// 遍历链表，找到最后
    		while (true) { 
    			// 找到链表的最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 如果没有找到最后, 将将temp后移
    			temp = temp.next;
    		}
    		// 当退出while循环时，temp就指向了链表的最后
    		// 形成一个双向链表
    		temp.next = newNode;
    		newNode.pre = temp;
    	}
    
    	// 添加节点到双向链表，考虑编号顺序时
    	// (如果对应编号上，有数据，则添加失败)
    	public void addByOrder(Node2 newNode) { 
    		// 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置
    		Node2 temp = head;
    		boolean flag = false; // 判断添加的编号是否存在，默认为false
    		while (true) { 
    			// 当temp已经在链表的最后，退出即可。因为新节点肯定在最后
    			if (temp.next == null) { 
    				break;
    			}
    			// 位置找到，就在temp的后面插入
    			if (temp.next.no > newNode.no) { 
    				break;
    			}
    			// 说明希望添加的节点的编号已经存在
    			else if (temp.next.no == newNode.no) { 
    				flag = true; // 说明编号存在
    				break;
    			}
    			temp = temp.next; // 后移，遍历当前链表
    		}
    		// 判断flag的值
    		// 不能添加，说明编号存在
    		if (flag) { 
    			System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no);
    		}
    		// 可以插入
    		else { 
    			// 插入到链表中, 形成双向链表
    			newNode.next = temp.next;
    			newNode.pre = temp;
    			// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
    			if (temp.next != null) { 
    				temp.next.pre = newNode;
    			}
    			temp.next = newNode;
    		}
    	}
    
    	// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
    	// 只是 节点类型改成 Node2
    	public void update(Node2 newNode) { 
    		// 判断是否空
    		if (head.next == null) { 
    			System.out.println("链表为空~");
    			return;
    		}
    		// 找到需要修改的节点, 根据no编号
    		// 定义一个辅助变量
    		Node2 temp = head.next;
    		boolean flag = false; // 表示是否找到该节点
    		while (true) { 
    			if (temp == null) { 
    				break; // 已经遍历完链表
    			}
    			if (temp.no == newNode.no) { 
    				// 找到
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		// 根据flag 判断是否找到要修改的节点
    		if (flag) { 
    			temp.data = newNode.data;
    		} else {  // 没有找到
    			System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
    		}
    	}
    
    	// 从双向链表中删除一个节点
    	public void del(int no) { 
    		// 判断当前链表是否为空
    		if (head.next == null) { // 空链表
    			System.out.println("链表为空，无法删除");
    			return;
    		}
    		Node2 temp = head.next; // 辅助变量
    		boolean flag = false; // 标志是否找到待删除节点
    		while (true) { 
    			if (temp == null) {  // 已经到链表的最后
    				break;
    			}
    			if (temp.no == no) { 
    				// 找到的待删除节点的前一个节点temp
    				flag = true;
    				break;
    			}
    			temp = temp.next; // temp后移
    		}
    		// 判断flag
    		if (flag) { 
    			// 可以删除
    			temp.pre.next = temp.next;
    			// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
    			if (temp.next != null) { 
    				temp.next.pre = temp.pre;
    			}
    		} else { 
    			System.out.printf("要删除的 %d 节点不存在\n", no);
    		}
    	}
    
    }
    
    // 定义Node2 ， 每个Node对象就是一个节点
    class Node2 { 
    	public int no;
    	public String data;
    	public Node2 next; // 指向下一个节点, 默认为null
    	public Node2 pre; // 指向前一个节点, 默认为null
    
    	// 构造器
    	public Node2(int no, String data) { 
    		this.no = no;
    		this.data = data;
    	}
    
    	@Override
    	public String toString() { 
    		return "Node [no=" + no + ", data=" + data + "]";
    	}
    
    }

--------------------

# 单向环形链表（约瑟夫问题） #

**Josephu 问题：**

设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

**分析：**

用一个不带头结点的循环链表可以处理Josephu 问题。

（1）构建一个单向的环形链表思路：

①先创建第一个节点，再建一个 first 节点，让 first 指向该节点。first ，就类似于链表的头节点的作用，找到这个单向环形链表的第一个节点 。  
②再让它自己的 next 指向它自己，形成一个环形。  
③之后，当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。（就相当于单向链表直接在链表尾部添加节点，只不过这个最后一个节点还有它的指向，即指向第一个节点）

（2）遍历环形链表思路：

①先让一个辅助变量 cur，指向first节点 。  
②然后通过一个while循环遍历 该环形链表即可 。直到 cur.next == first 结束 。

（3）对于本问题，还需要一些其他的考虑。first 的指向需要一直移动。因为经过循环很有可能会删除first指向的节点，从而导致判断出现问题。因为我们判断什么时候结束，需要看链表什么时候为空，以前是判断head.next==null即可，而且是存在头指针的。但是假如这里使用判断为空的方法，又需要判断它是最后一个节点，因为如果不判断，像之前单向链表一样，我们所谓的删除就只是移动next指针，把要删除的节点移出，不是“真删除”，当只剩一个节点时，因为它是循环的，所以它的next总有值，所以需要判断它是最后一个节点，这样就意味着算法结束。这样显然很麻烦。不如在最开始时，就添加一个，可以指向最后一个节点的变量（指针）。 什么时候结束，只需要判断，当最后一个节点指针的指向 和 第一个指针的指向 都 指向了同一个节点，那也就意味着只有一个节点，也就意味着结束。

（4）所以，我们创建一个辅助指针(变量) helper ， 事先指向环形链表的最后一个节点。那么，算法开始时，先让 first 和 helper 移动 k - 1次。当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次。这时将first 指向的小孩节点出圈：  
first = first .next  
helper.next = first  
（原来first 指向的节点就没有任何引用，就会被回收）  
直到 first==helper 就结束了。

--------------------

比如：  
一共5个小孩，编号为：1、2、3、4、5。现在first指向第1个小孩，helper指向第5个小孩。现在从第1个小孩开始，当报数为2时，这个小孩出列。

算法开始时，先让 first 和  helper 移动 k - 1次。
    当小孩报数时，让first 和 helper 指针同时 的移动  m  - 1 次。
    这时将first 指向的小孩节点出列，然后：
    first = first .next 
    helper.next = first  
    直到 first==helper 就结束了。

验证如下：（k=1，m=2）  
①first和helper移动0次，现在first指向第1个小孩，helper指向第5个小孩。  
②开始报数

（1）first和helper同时移动1次，现在first指向第2个小孩，helper指向第1个小孩，first指向的第2个小孩出列。然后first指向第3个小孩，helper指向第1个小孩。现在链表中，有1、3、4、5。

（2）first和helper同时移动1次，现在first指向第4个小孩，helper指向第3个小孩，first指向的第4个小孩出列。然后first指向第5个小孩，helper指向第3个小孩。现在链表中，有1、3、5。

（3）first和helper同时移动1次，现在first指向第1个小孩，helper指向第5个小孩，first指向的第1个小孩出列。然后first指向第3个小孩，helper指向第5个小孩。现在链表中，有3、5。

（4）first和helper同时移动1次，现在first指向第5个小孩，helper指向第3个小孩，first指向的第5个小孩出列。然后first指向第3个小孩，helper指向第3个小孩。现在链表中，有3。

③因为first==helper，所以算法结束，最后一个出列的就是3。

--------------------

## 完整代码 ##

public class Josepfu { 
    
    	public static void main(String[] args) { 
    		// 测试构建环形链表和遍历是否正确
    		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
    		circleSingleLinkedList.addBoy(125);// 加入125个小孩节点
    		circleSingleLinkedList.showBoy();
    		
    		//测试小孩出圈是否正确
    		circleSingleLinkedList.countBoy(10, 20, 125); 
    	}
    
    }
    
    // 创建一个环形的单向链表
    class CircleSingleLinkedList { 
    	// 创建一个first节点,当前没有编号
    	private Boy first = null;
    
    	// 添加小孩节点，构建成一个环形的链表
    	public void addBoy(int nums) { 
    		// nums 做一个数据校验
    		if (nums < 1) { 
    			System.out.println("nums的值不正确");
    			return;
    		}
    		Boy cur = null; // 辅助变量，帮助构建环形链表
    		// 使用for来创建环形链表
    		for (int i = 1; i <= nums; i++) { 
    			// 根据编号，创建小孩节点
    			Boy boy = new Boy(i);
    			// 如果是第一个小孩
    			if (i == 1) { 
    				first = boy;
    				first.setNext(first); // 构成环
    				cur = first; // 让cur指向第一个小孩
    			} 
    			else { 
    				cur.setNext(boy);
    				boy.setNext(first);
    				cur = boy;
    			}
    		}
    	}
    
    	// 遍历当前的环形链表
    	public void showBoy() { 
    		// 判断链表是否为空
    		if (first == null) { 
    			System.out.println("没有任何小孩");
    			return;
    		}
    		// 因为first不能动，因此我们仍然使用一个辅助变量来完成遍历
    		Boy cur = first;
    		while (true) { 
    			System.out.printf("小孩的编号 %d \n", cur.getNo());
    			if (cur.getNext() == first) { // 说明已经遍历完毕
    				break;
    			}
    			cur = cur.getNext(); // curBoy后移
    		}
    	}
    
    	// 根据用户的输入，计算出小孩出圈的顺序
    	/** * startNo 表示从第几个小孩开始数数 * countNum 表示数几下 * nums 表示最初有多少小孩在圈中 */
    	public void countBoy(int startNo, int countNum, int nums) { 
    		// 先对数据进行校验
    		if (first == null || startNo < 1 || startNo > nums) { 
    			System.out.println("参数输入有误， 请重新输入");
    			return;
    		}
    		// 创建一个辅助变量 helper , 指向环形链表的最后这个节点
    		Boy helper = first;
    		while (true) { 
    			if (helper.getNext() == first) {  // 说明helper指向最后小孩节点
    				break;
    			}
    			helper = helper.getNext();
    		}
    		//小孩报数前，先让 first 和 helper 移动 k - 1次
    		for(int j = 0; j < startNo - 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.getNo());
    			//这时将first指向的小孩节点出圈
    			first = first.getNext();
    			helper.setNext(first); 
    		}
    		System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());	
    	}
    }
    
    // 创建一个Boy类，表示一个节点
    class Boy { 
    	private int no;// 编号
    	private Boy next; // 指向下一个节点,默认null
    
    	public Boy(int no) { 
    		this.no = no;
    	}
    
    	public int getNo() { 
    		return no;
    	}
    
    	public void setNo(int no) { 
    		this.no = no;
    	}
    
    	public Boy getNext() { 
    		return next;
    	}
    
    	public void setNext(Boy next) { 
    		this.next = next;
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200225104509868.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200225105137710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx,size_16,color_FFFFFF,t_70
[20200225131842155.png]: https://img-blog.csdnimg.cn/20200225131842155.png