开心学算法的第四天
环形单链表
环形列表结构
构造环形列表
class singleLinked<E>{
//环形列表头节点
private Node<E> head;
//环形列表元素个数
private int size;
class Node<E>{
private E val;
private Node<E> next;
public Node(E val){
this.val = val;
}
}
}
添加元素
//添加元素
public void add(E val){
//如果是空链表
if (head == null){
head = new Node<>(val);
head.next = head;
size++;
return;
}
//非空链表常规操作
Node newNode = new Node(val);
//缓存头节点
Node node = head;
//遍历至尾结点出
while (node.next != head){
node = node.next;
}
//将节点加在尾部
node.next = newNode;
newNode.next = head;
size++;
}
删除元素
删除元素：分三种情况
1.删除头节点
删除头节点要找到链表的最后一个节点，然后head后移一个也就是
head = head.next，然后使最后一个节点的next指向head即可。
2.删除链表仅有的一个节点
这里需要用size进行判断，我的size先进行了减减操作，所有条件是
size == 0就可以直接head= null删除成功直接返回。
3.删除常规的节点
定义一个快指针node，慢指针low然后然后找到要删除的节点，使用
low = low.next就可以删除当前node节点。
//删除指定位置元素
public boolean remove(E val){
//判断链表为空
if (head == null){
System.out.println("链表为空删除失败");
return false;
}
size--;
//删除头节点
if (head.val == val && size != 0){
//找到尾结点
Node tail = head;
while (tail.next != head){
tail = tail.next;
}
head = head.next;
tail.next = head;
return true;
}else if (size == 0){
//表示的是删除最后一个节点
head = null;
return true;
} else{
//删除平常节点
Node node = head;
Node low = head;
while(node.val != val){
low = node;
node = node.next;
}
low.next = low.next.next;
return true;
}
}
打印当前链表
//打印链表
public void showLinked(){
if (head == null){
System.out.println("链表为空");
return;
}
Node node = head;
int index = 0;
while(index++ < size){
System.out.print(node.val+" ");
node = node.next;
}
}
获取节点个数
//获取链表有效个数
public int getSize(){
return this.size;
}
所有代码
class singleLinked<E>{
private Node<E> head;
private int size;
class Node<E>{
private E val;
private Node<E> next;
public Node(E val){
this.val = val;
}
}
//添加元素
public void add(E val){
//如果是空链表
if (head == null){
head = new Node<>(val);
head.next = head;
size++;
return;
}
//非空链表常规操作
Node newNode = new Node(val);
//缓存头节点
Node node = head;
//遍历至尾结点出
while (node.next != head){
node = node.next;
}
//将节点加在尾部
node.next = newNode;
newNode.next = head;
size++;
}
//删除指定位置元素
public boolean remove(E val){
//判断链表为空
if (head == null){
System.out.println("链表为空删除失败");
return false;
}
size--;
//删除头节点
if (head.val == val && size != 0){
//找到尾结点
Node tail = head;
while (tail.next != head){
tail = tail.next;
}
head = head.next;
tail.next = head;
return true;
}else if (size == 0){
//表示的是删除最后一个节点
head = null;
return true;
} else{
//删除平常节点
Node node = head;
Node low = head;
while(node.val != val){
low = node;
node = node.next;
}
low.next = low.next.next;
return true;
}
}
//打印链表
public void showLinked(){
if (head == null){
System.out.println("链表为空");
return;
}
Node node = head;
int index = 0;
while(index++ < size){
System.out.print(node.val+" ");
node = node.next;
}
}
//获取链表有效个数
public int getSize(){
return this.size;
}
}
约瑟夫环问题
问题描述：
num个人围成一圈对其进行编号从第一个人开始报数，每当到第count个时当前这个人出局，然后下一个人从1开始继续依次类推到最后剩余的那个人，打印出剩余那个人的编号。
数组解法
/**
* 问题描述：
* num个人围成一圈从第一个人开始报数，每当到第count个时当前这个人出局
* 然后下一个人从1开始继续依次类推到最后剩余的那个人，打印出剩余那个人的编号
* @param num 表示一个几个人
* @param count 报的数字
*/
public static void joseph(int num,int count){
//初始化arr数组
int[] arr = new int[num];
for (int i = 0; i < arr.length; i++) {
arr[i] = i+1;
}
//创建相同长度的boolean数组标记是否已经出局
boolean[] flag = new boolean[arr.length];
//查看数组中剩余的元素
int residue = arr.length;
//用来计数
int number = 1;
while(residue != 1){
for (int i = 0;i < arr.length;i++){
if (number % count == 0 && !flag[i]){
flag[i] = true;
residue--;
number++;
}
if (flag[i]){
continue;
}
number++;
}
}
//打印最后一个元素
for (int i = 0; i < arr.length; i++) {
if (!flag[i]){
System.out.println("最后一个元素"+arr[i]);
}
}
}
链表解法
使用上面的环形链表即可求解。
循环的条件直接是getsize == 1就可以判断当前只剩一个人，每次移除掉指定节点即可，这种做法相对于数组的解法简单且清晰。
//约瑟夫环问题
public void joseph(int num,int count){
//构建链表
Node node = head;
int i = 1;
while (getSize() != 1){
if (i%count==0) {
remove((E) node.val);
}
i++;
node = node.next;
}
System.out.println(head.val);
}
点个赞呗~
