7.1练习:
类方法:
public class test{ private class Node{ Node next; //指针 int item; //数据 public Node(int item,Node next){ this.next=next; this.item=item; } }//定义节点 Node head;//定义头节点 int size; //定义长度 public test(){ int size=0; //对长度进行初始化 } public int getSize(){ return size; } public Node getNode(int idex){ Node target=this.head.next; for(int i=0;i<idex;i++){ target=target.next; } return target; }//获得结点 public int get(int idex){ return getNode(idex).item; }//获得值 public void add(int t){ Node node=new Node(t,null); if(this.size==0){ this.head.next=node; }else{ getNode(this.size-1).next=node; } this.size++; } }
主方法:
import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs) { LinkedList s=new LinkedList<>(); Scanner sc=new Scanner(System.in); System.out.println("请输入您的数据"); for(int i=0;i<100;i++){ int m=sc.nextInt(); s.add(m); if(s.get(i).equals(-1)){ System.out.println("链表创建完毕！"); break; } } System.out.println("链表的数据为:"); for (int i=0;i<s.size();i++){ System.out.print(s.get(i)+" "); } } }
8.循环链表(双指针快慢)
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
8.1判断是否是循环链表
利用快慢指针判断是否这个链表是否为环形
基本思路:
因为快指针比慢指针走的快，慢指针比快指针走的慢。会有多次相遇的机会的
方法:
public boolean QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 Node1 quick=this.head.next; while(quick!=null&&quick.next!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; if(quick!=null&&quick.equals(slow)){ return true; } } return false; }
//创建环形链表:
只需要把你想要的结点的指针指向你要循环的地方，就可以构成一个循环链表.
public void Recle(int start,int end){ Node1 node=getNode(start); Node1 node1=getNode(end); node1.next=node; }
全部代码:
主方法: import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs) { LinkedList<String> s=new LinkedList<>(); //构造一个单链表 s.add("aa"); s.add("cc"); s.add("ee"); s.add("zz"); System.out.println(s.QuickSlowP()); //构造一个环形链表 s.Recle(2,s.size()-1); System.out.println(s.QuickSlowP()); } } 类方法 import org.jetbrains.annotations.NotNull; public class LinkedList<T> { Node1 head; //设置头节点 int size; //链表长度 public LinkedList() { //初始化链表 this.head=new Node1(null,null); this.size=0; } public void Recle(int start,int end){ Node1 node=getNode(start); Node1 node1=getNode(end); node1.next=node; } //使用快慢指针寻找中间元素 public boolean QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 Node1 quick=this.head.next; while(quick!=null&&quick.next!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; if(quick!=null&&quick.equals(slow)){ return true; } } return false; } //获取当前链表的长度: public int size(){ return this.size; } //获取指定位置的元素: public T get(int idex){ Node1 target=this.head.next; //获取0结点的指针，且目前表示的是第一个结点 for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target.item; } //获取指定位置的结点 public Node1 getNode(int idex){ if(idex==-1){ //目的是在指定位置0的时候的作用 return head; } Node1 target=this.head.next; for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target; } //在尾部添加数据 public void add(T t){ Node1 node=new Node1(t,null); if(this.size==0){ //假如说是0结点，那么就添加到零结点 this.head.next=node; }else { //找到最后一个结点 this.getNode(this.size-1).next=node; } //链表长度++ this.size++; } //在指定位置插入数据 private class Node1 { //调用结点类 T item; //数据域 Node1 next; //指针域 public Node1(T item, Node1 next) { this.item = item; this.next = next; } }//调用节点类 }
8.2求循环链表的入口元素
基本思路:
首先我们要判断这个链表是否是一个循环链表，如果是循环链表的话那么我们就继续执行操作，不是循环链表的话返回一个NULL。判断是否是入口的关键就在于慢指针slow，和一个新的指针（从第一个元素开始）往后遍历，如果新的指针和指针slow相交的位置，就是元素的所在位置.
public T QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 int length=-1; int a=0; Node1 quick=this.head.next; while(quick!=null&&quick.next!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; if(quick!=null&&quick.equals(slow)){ //假如环形 Node1 entry=this.head.next; //定义一个新的指针 while(!entry.equals(slow)){ entry=entry.next; slow=slow.next; } return entry.item; } } return null; }
8.3指定点循环链表的建立
public void Recle(int start,int end){ Node1 node=getNode(start); //开始点 Node1 node1=getNode(end); //结束点 node1.next=node; //首尾相连接 }
8.4不指定点循环链表建立
public void SolveYsf (int m,int n){ //m是元素的个数，n是间隔几个 //建立一个链表 for(int i=1;i<=m;i++){ //添加链表的元素 add((T)(i+"")); } //进行加环处理 Node1 node=getNode(0); Node1 node1=getNode(this.size-1); node1.next=this.head.next;
8.5约瑟夫问题
进行自杀操作，一共m个人，没间隔n个，那么就第n个人进行自杀操作。
public void SolveYsf (int m,int n){ //建立一个链表 for(int i=1;i<=m;i++){ //添加链表的元素 add((T)(i+"")); } //进行加环处理 Node1 node=getNode(0); Node1 node1=getNode(this.size-1); node1.next=this.head.next; //开始处理约瑟夫问题 Node1 target=this.head.next; int cn=1; while(target!=target.next){ //获取前一个元素 Node1 prev=target; //获取中间元素的前一个位置 //游标进行后移 target=target.next; //获取中间元素 //计算 cn++; if(cn==n){ //假如说cn=指定的n，那么就自杀 System.out.println("需要移除的元素是:"+target.item); prev.next=target.next; //把中间元素的前一个元素指向中间元素后一个元素 target=target.next; //把中间元素指向中间元素的后一个元素. cn=1; } } System.out.println("保留的元素是:"+target.item); }
