1000个人，从1数到3，数到3的出局，来回循环。最后剩下的是多少

灰太狼 2022-05-12 04:34 113阅读 0赞

1、把每个人看做一个节点，每个节点存储数字和下一个节点

2、把左右的节点构造一个环

3、遍历环

第一步，构造节点

public class Node \{  
    private int data;  
    private Node next;  
    public int getData() \{  
        return data;  
    \}  
    public void setData(int data) \{  
        this.data = data;  
    \}  
    public Node getNext() \{  
        return next;  
    \}  
    public void setNext(Node next) \{  
        this.next = next;  
    \}  
      
\}

第二步 构造环，并返回开始节点

private static Node createList(int cnt) \{  
        // 根节点  
        Node rootNode = new Node();   
        rootNode.setData(1);  
        Node currentNode = rootNode;  
        for (int i = 2; i <= cnt; i++) \{  
            Node node = new Node();  
            node.setData(i);  
            currentNode.setNext(node);  
            currentNode = node;  
        \}  
        // 最后一个节点指向根节点，形成一个闭环  
        currentNode.setNext(rootNode);  
        return rootNode;  
    \}

第三步  遍历环，并返回最终剩余的节点数据

public static void main(String\[\] args) \{  
        // 构建一个环，并返回开始节点  
        Node currNode = createList(1000);  
        // 当剩余的节点指向自己的时候，说明就剩一个节点了  
        while(currNode.getNext() != currNode) \{  
            // 获取当前节点往后数第四个节点  
            Node tmpNode = currNode.getNext().getNext().getNext();  
            // 当前节点往后的第二个节点指向上面取到的第四个节点（数到三的退出）  
            currNode.getNext().setNext(tmpNode);  
            // 第四个节点作为当前节点，继续数数  
            currNode = tmpNode;  
        \}  
        System.out.println(currNode.getData());  
    \}