1047: [编程入门]报数问题-单循环链表（Java）

解题思路: 先构造一个单循环链表，之后循环删除就可以了。不需要像数组一样，节省了位移的时间。

参考代码:

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		// 构造一个单循环链表
		Node head = new Main.Node();
		Node p = head;
		for(int i =1;i<n;i++) {
			p.number = i;
			p.next = new Main.Node();
			p=p.next;
		}
		p.number = n;
		p.next  = head;
		
		// 循环删除直至最后一个
		p = head;
		// 待删除节点的前一个节点
		Node temp = null;
		while(p.next != p) {
			temp  = p.next;
			temp.next = p.next.next.next;
			p = temp.next;
		}
		System.out.println(p.number);
	}
	
	static class  Node{
		public int number;
		public Node next;
	}
}