环形单链表

怼烎@ 2021-08-11 19:26 457阅读 0赞

【一】环形单链表

> 单项环形链表解决约瑟夫环  
> 1.定义节点  
> 2.创建环形链表  
> 3.遍历环形链表  
> 4.环形链表添加节点

【二】环形单链表的图示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70][]

【三】代码实现

public class LinkedListDemo {
    	public static void main(String[] args) {
    		CirLinkedList cll=new CirLinkedList();
    		cll.addNodes(10);
    		cll.NodesList(cll);
    		System.out.println("约瑟夫环的问题解决：");
    		cll.Joseph(2,3,10);
    	}
    }
    
    //创建链表
    class CirLinkedList{
    	private LinkedNode first=null;
    	//约瑟夫操作
    	/*
    	 *startNo表示开始数数的位置 
    	 * countNum表示数几下
    	 * nums表示最初多少个节点
    	 */
    	public void Joseph(int startNo,int countNum,int nums) {
    		if(first==null||startNo<1||startNo>nums) {
    			System.out.println("参数有误,请重新输入");
    			return;
    		}
    		LinkedNode temp=first;//创建辅助指针
    		//while操作的目的是为了让temp节点位于first节点之前
    		while(true) {
    			if(temp.getNext()==first) {
    				break;
    			}
    			temp=temp.getNext();
    		}
    		//将first指针移至startNo表示开始数数的位置 
    		for(int j=0;j<startNo-1;j++) {
    			first=first.getNext();
    			temp=temp.getNext();
    		}
    		//出圈规则
    		while(true) {
    			if(temp==first) {
    				break;
    			}
    			for(int j=0;j<countNum-1;j++) {
    				first=first.getNext();
    				temp=temp.getNext();
    			}
    			System.out.printf("节点%d出圈\n", first.getValue());
    			first=first.getNext();
    			temp.setNext(first);
    		}
    		System.out.printf("最后留在圈中的节点是%d\n",temp.getValue());
    	}
    	
    	//添加节点
    	public void addNodes(int nums) {
    		if(nums<1) {
    			System.out.println("输入的数值小于零，不能用来建表");
    			return;
    		}
    		LinkedNode temp=null;//辅助指针
    		for(int i=1;i<=nums;i++) {
    			LinkedNode node=new LinkedNode(i);
    			if(i==1) {
    				first=node;
    				first.setNext(first);
    				temp=first;
    			}else {
    				temp.setNext(node);
    				node.setNext(first);
    				temp=node;
    			}
    		}
    	}
    	
    	//遍历节点
    	public void NodesList(CirLinkedList cll) {
    		if(first==null) {
    			System.out.println("没有节点，环形链表为空");
    			return;
    		}
    		LinkedNode temp=first;
    		while(true) {
    			System.out.print(temp+"\t");
    			if(temp.getNext()==first) {
    				System.out.println();
    				break;
    			}
    			temp=temp.getNext();
    		}
    	}
    }
    
    //定义链表的节点
    class LinkedNode{
    	private int value;
    	private LinkedNode next;
    	
    	public LinkedNode(int value){
    		this.value=value;
    	}
    	
    	public int getValue() {
    		return value;
    	}
    
    	public void setValue(int value) {
    		this.value = value;
    	}
    
    	public LinkedNode getNext() {
    		return next;
    	}
    
    	public void setNext(LinkedNode next) {
    		this.next = next;
    	}
    
    	public String toString() {
    		return "["+value+"]";
    	}
    }

【四】输出截图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70]: /images/20210811/9db783b4772e4c3d98ef935f053251a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1]: /images/20210811/10dcf4b608194dceb98c09497b83264a.png