题解 | #删数# | 构造环形链表

既然还没有Java的，那我先来。

使用链表数据结构。难的是怎么构造环形链表，一旦构造出来就简单多了。有没有思路更简单的方法？

import java.util.Scanner;

public class Main {
    public static class List {
        List pre;
        List nxt;
        int val;
        List(int val) {
            this.val = val;
        }
    }
    static List root;
    static List lastP;
    static int length = 1;
    static int res;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            length = in.nextInt();
            if (length == 1) System.out.println(0);

            root = ConstructList(null, 0);
            root.pre = lastP;
            lastP.nxt = root;

            Delet(root.nxt.nxt);
            System.out.println(res);
        }
        in.close();
    }

  //构造环形链表
    public static List ConstructList(List preP, int val) {
        List p = new List(val);
        p.pre = preP;
        if (val == length - 1) {
            lastP = p;
            return p;
        }
        p.nxt = ConstructList(p, ++val);
        return p;
    }

    public static void Delet(List p) {
        p.pre.nxt = p.nxt;
        p.nxt.pre = p.pre;
        if (p.nxt == p.nxt.nxt) {
            res = p.nxt.val;
            return;
        }
        Delet(p.nxt.nxt.nxt);
    }
}