开心学算法的第四天
环形单链表
环形列表结构
构造环形列表
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);}
点个赞呗~