Java实现循环链表，约瑟夫环，判断链表有无环等问题

Bertha 。 2023-07-08 15:27 30阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

## 一 循环链表 ##

首先用Java实现循环链表及其增删改查等操作：

public class CircularList<T>{
        
    
    	private class Node{
        
    		Node next = null;
    		T data;
    		public Node(T t) {
        
    			this.data = t;
    		}
    	}
    	private Node head;
    	private int len;
    	public CircularList() {
        
    		this.head = new Node(null);
    		this.len = 0;
    		this.head.next = head;
    	}
    	//获取第Index个节点
    	public Node getNode(int index) {
        
    		if(index<0 || index>len) {
        
    			throw new ArrayIndexOutOfBoundsException("Index error");
    		}
    		Node temp = head;
    		for(int i=0;i<index;i++) {
        
    			temp = temp.next;
    		}
    		return temp;
    	}
    	//向指定位置后面插入节点
    	public boolean insert(T t, int index) {
        
    		if(index<0 || index>len) {
        
    			System.out.println("Delete failed, Index error!");
    			return false;
    		}
    		Node temp = getNode(index);
    		Node node = new Node(t);
    		node.next = temp.next;
    		temp.next = node;
    		this.len++;
    		return true;
    	}
    	//向链表尾部加入节点
    	public void addTail(T t) {
        
    		Node node = new Node(t);
    		Node temp = getNode(len);
    		node.next = temp.next;
    		temp.next = node;
    		this.len++;
    	}
    	//删除指定位置的节点
    	public T delete(int index) {
        
    		if(index<0 || index>len) {
        
    			throw new ArrayIndexOutOfBoundsException("Index error");
    		}
    		Node prev = getNode(index - 1);
    		T t = prev.next.data;
    		prev.next = prev.next.next;
    		len--;
    		return t;
    	}
    	//修改指定位置节点的值
    	public boolean change(T t, int index) {
        
    		if(index<0 || index>len) {
        
    			System.out.println("Change failed, Index error!");
    			return false;
    		}
    		Node temp = getNode(index);
    		temp.data = t;
    		return true;
    	}
    	//查找指定位置的值
    	public T find(int index) {
        
    		Node temp = getNode(index);
    		return temp.data;
    	}
    	//将循环链表cl2连接到cl1
    	public CircularList connect(CircularList cl1, CircularList cl2) {
        
    		Node last1 = cl1.getNode(cl1.len);
    		Node first2 = cl2.head.next;
    		Node last2 = cl2.getNode(cl2.len);
    		last1.next = first2;
    		last2.next = cl1.head;
    		cl1.len = cl1.len + cl2.len;
    		return cl1;
    	}
    
    	//输出链表
    	public void print() {
        
    		Node temp = head;
    		for(int i=0;i<=len;i++) {
        
    			System.out.print(temp.data + " ");
    			temp = temp.next;
    		}
    		 System.out.print(" length:" + len + "\n");
    	}
    }

## 二 约瑟夫环问题 ##

/**
    	 * 约瑟夫环问题，依次输出出列的节点的数据
    	 * @param k 间隔人数，经典约瑟夫问题k=3
    	 */
    	public void Josephus(int k) {
        
    		Node last = getNode(len);
    		//将尾节点指向第一个节点而不是首节点
    		last.next = head.next;
    		Node temp = head;
    		while(temp.next != temp) {
        
    			//找到第k个节点的前一个节点
    			for(int i=0; i<k-1; i++) {
        
    				temp = temp.next;
    			}
    			T t = temp.next.data;
    			//将第k-1个节点指向第k+1个节点,即删除第k个节点
    			temp.next = temp.next.next;
    			len--;
    			System.out.print(t + "->");
    		}
    		System.out.println(temp.data);
    	}

约瑟夫环的衍生问题，每个人持有一个密码M，报到M的人出列。  
解决方法：将上面的代码的Node节点增加一个属性用于存放密码M，然后将上面for循环的k替换为出列的人的密码M即可，这里就不给出代码了。

## 三 判断链表是否有环 ##

方法一：比较步数法。设置一个指针p，每次走一步，记录总步数count1；设置指针q，每次都从头指针往前走，直到走到和p相同的节点，记录q走过的步数为count2。若链表有环时，当p指针绕环一圈走到环的切入点，指针q不需要进环即可走到环的切入点，此时count1不等于count2。因此，当两个指针步数不同时链表有环。

//用比较步数法判断是否有环
    	public boolean checkLoop2() {
        
    		Node p = head;
    		Node q = head;
    		int count1 = 0;
    		int count2 = 0;
    		while(p != null) {
        
    			p = p.next;
    			count1++;
    			q = head;
    			count2 = 0;
    			while(p != q) {
        
    				q = q.next;
    				count2++;
    			}
    			if(count1 != count2) {
        
    				System.out.println(count2);
    				return true;
    			}
    		}
    		return false;
    	}

方法二：快慢指针法，设置快指针fast和慢指针slow，每次快指针走两步，慢指针走一步。若链表有环时，当两个指针都进入环中后，由于两个指针速度不同，它们一定会相遇。  
链表有环时的衍生问题。参考链接：[点击进入][Link 1]  
衍生问题一：求环的切入点的位置。当两个指针相遇后，将慢指针slow放到头指针head处，快指针不动，当他们再次相遇时的节点就是环的切入点。论证过程见博主：[点击进入][Link 2]  
衍生问题二：求环上节点的个数。将两个指针都放在环的切入点上，慢指针不动，快指针每次移动一步，当再次相遇时快指针走过的步数就是环的长度。  
衍生问题三，链表的长度。简单不写。

//用快慢指针判断链表是否有环
    	public void checkLoop1() {
        
    		Node fast = head;
    		Node slow = head;
    		boolean judge = false;
    		while(slow != null && fast != null && fast.next != null) {
        
    			fast = fast.next.next;
    			slow = slow.next;
    			if(fast == slow) {
        
    				System.out.println("链表有环");
    				judge = true;
    				break;
    			}
    		}
    		if(!judge) {
        
    			System.out.println("链表无环");
    			return;
    		}
    		//若链表有环
    		
    		//衍生问题一，环的切入点的位置：
    		//slow回到head，fast不动，这次fast和slow每次都走一步，再次相遇时就是环的切入点
    		slow = head;
    		int count1 = 0;
    		while(slow != fast) {
        
    			slow = slow.next;
    			fast = fast.next;
    			count1 ++;
    		}
    		System.out.println("环的切入点是第" + count1 + "个节点，值为：" + slow.data);
    		
    		//衍生问题二，环上节点的个数
    		int count2 = 1;
    		fast = fast.next;
    		while(slow != fast) {
        
    			fast = fast.next;
    			count2 ++;
    		}
    		System.out.println("环上有" + count2 + "个节点");
    		
    		//衍生问题三，链表的长度
    		int num = count1 + count2 - 1;
    		System.out.println("链表长度为：" + num);
    	}

## 所有代码 ##

package day2_24;
    
    public class CircularList<T>{
        
    
    	private class Node{
        
    		Node next = null;
    		T data;
    		public Node(T t) {
        
    			this.data = t;
    		}
    	}
    	private Node head;
    	private int len;
    	public CircularList() {
        
    		this.head = new Node(null);
    		this.len = 0;
    		this.head.next = head;
    	}
    	//获取第Index个节点
    	public Node getNode(int index) {
        
    		if(index<0 || index>len) {
        
    			throw new ArrayIndexOutOfBoundsException("Index error");
    		}
    		Node temp = head;
    		for(int i=0;i<index;i++) {
        
    			temp = temp.next;
    		}
    		return temp;
    	}
    	//向指定位置后面插入节点
    	public boolean insert(T t, int index) {
        
    		if(index<0 || index>len) {
        
    			System.out.println("Delete failed, Index error!");
    			return false;
    		}
    		Node temp = getNode(index);
    		Node node = new Node(t);
    		node.next = temp.next;
    		temp.next = node;
    		this.len++;
    		return true;
    	}
    	//向链表尾部加入节点
    	public void addTail(T t) {
        
    		Node node = new Node(t);
    		Node temp = getNode(len);
    		node.next = temp.next;
    		temp.next = node;
    		this.len++;
    	}
    	//删除指定位置的节点
    	public T delete(int index) {
        
    		if(index<0 || index>len) {
        
    			throw new ArrayIndexOutOfBoundsException("Index error");
    		}
    		Node prev = getNode(index - 1);
    		T t = prev.next.data;
    		prev.next = prev.next.next;
    		len--;
    		return t;
    	}
    	//修改指定位置节点的值
    	public boolean change(T t, int index) {
        
    		if(index<0 || index>len) {
        
    			System.out.println("Change failed, Index error!");
    			return false;
    		}
    		Node temp = getNode(index);
    		temp.data = t;
    		return true;
    	}
    	//查找指定位置的值
    	public T find(int index) {
        
    		Node temp = getNode(index);
    		return temp.data;
    	}
    	//将循环链表cl2连接到cl1
    	public CircularList connect(CircularList cl1, CircularList cl2) {
        
    		Node last1 = cl1.getNode(cl1.len);
    		Node first2 = cl2.head.next;
    		Node last2 = cl2.getNode(cl2.len);
    		last1.next = first2;
    		last2.next = cl1.head;
    		cl1.len = cl1.len + cl2.len;
    		return cl1;
    	}
    
    	//输出链表
    	public void print() {
        
    		Node temp = head;
    		for(int i=0;i<=len;i++) {
        
    			System.out.print(temp.data + " ");
    			temp = temp.next;
    		}
    		 System.out.print(" length:" + len + "\n");
    	}
    	
    	/**
    	 * 约瑟夫环问题，依次输出出列的节点的数据
    	 * @param k 间隔人数，经典约瑟夫问题k=3
    	 */
    	public void Josephus(int k) {
        
    		Node last = getNode(len);
    		//将尾节点指向第一个节点而不是首节点
    		last.next = head.next;
    		Node temp = head;
    		while(temp.next != temp) {
        
    			//找到第k个节点的前一个节点
    			for(int i=0; i<k-1; i++) {
        
    				temp = temp.next;
    			}
    			T t = temp.next.data;
    			//将第k-1个节点指向第k+1个节点,即删除第k个节点
    			temp.next = temp.next.next;
    			len--;
    			System.out.print(t + "->");
    		}
    		System.out.println(temp.data);
    	}
    	
    
    	//用比较步数法判断是否有环
    	public boolean checkLoop2() {
        
    		Node p = head;
    		Node q = head;
    		int count1 = 0;
    		int count2 = 0;
    		while(p != null) {
        
    			p = p.next;
    			count1++;
    			q = head;
    			count2 = 0;
    			while(p != q) {
        
    				q = q.next;
    				count2++;
    			}
    			if(count1 != count2) {
        
    				System.out.println(count2);
    				return true;
    			}
    		}
    		return false;
    	}
    	//用快慢指针判断链表是否有环
    	public void checkLoop1() {
        
    		Node fast = head;
    		Node slow = head;
    		boolean judge = false;
    		while(slow != null && fast != null && fast.next != null) {
        
    			fast = fast.next.next;
    			slow = slow.next;
    			if(fast == slow) {
        
    				System.out.println("链表有环");
    				judge = true;
    				break;
    			}
    		}
    		if(!judge) {
        
    			System.out.println("链表无环");
    			return;
    		}
    		//若链表有环
    		
    		//衍生问题一，环的切入点的位置：
    		//slow回到head，fast不动，这次fast和slow每次都走一步，再次相遇时就是环的切入点
    		slow = head;
    		int count1 = 0;
    		while(slow != fast) {
        
    			slow = slow.next;
    			fast = fast.next;
    			count1 ++;
    		}
    		System.out.println("环的切入点是第" + count1 + "个节点，值为：" + slow.data);
    		
    		//衍生问题二，环上节点的个数
    		int count2 = 1;
    		fast = fast.next;
    		while(slow != fast) {
        
    			fast = fast.next;
    			count2 ++;
    		}
    		System.out.println("环上有" + count2 + "个节点");
    		
    		//衍生问题三，链表的长度
    		int num = count1 + count2 - 1;
    		System.out.println("链表长度为：" + num);
    	}
    	
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		CircularList cl = new CircularList();
    		for(int i=1; i<=41; i++) {
        
    			cl.addTail(i);
    		}
    //		cl.Josephus(3);
    		
    		cl.getNode(cl.len).next = cl.head.next.next.next.next;
    		System.out.println(cl.checkLoop2());
    		cl.print();
    	}
    
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982
[Link 1]: https://www.cnblogs.com/dancingrain/p/3405197.html
[Link 2]: https://blog.csdn.net/u012534831/article/details/74231581