【java数据结构与算法学习】魔术师发牌问题

爱被打了一巴掌 2022-05-30 00:46 222阅读 0赞

魔术师发牌问题：

魔术师手里一共有13张牌，全是黑桃，1~13.魔术师需要实现一个魔术：这是十三张牌全部放在桌面上（正面向下）， 第一次摸出第一张，是1，翻过来放在桌面上。 第二次摸出从上往下数第二张，是2，翻过来 放在桌面上，（第一张放在最下面去，等会儿再摸）， 第三次摸出从上往下数第三张，是3，翻过来放在桌面上，（第一张和第二张 放在最下面去，等会儿再摸） 以此类推 最后一张就是13

魔术师发牌问题，我们可以用一个循环链表来实现，下面就是java的实现代码。

public class MagicCard {
        private static class Node{
            Integer data;
            Node next;
            public Node(){
    
            }
            public Node(Integer data, Node next){
                this.data = data;
                this.next = next;
            }
        }
        //创建不包含头节点的循环链表：其实就是先创建一个单链表，然后最后一个节点指向首节点
        public Node createList(int n){
            Node header = new Node(null,null);
            if (n == 0){
                return null;
            }
            Node p = header;
            Node newNode;
            for (int i = 0; i < n; i++) {
                newNode = new Node(0,null);
                p.next = newNode;
                p = p.next;
            }
            p.next = header.next;
            return p.next;
        }
        //得到魔术师牌组顺序
        public Node getCard(Node p, int num){
            Node header = p;
            //第一个数据
            p.data = 1;
            //我们从第二张开始记数
            int cardNum = 2;
            while (cardNum <= num){
                for (int i = 0;i<cardNum;i++){
                    p = p.next;
                    /*
                        如果当前元素不是0，说明我们遇到了已经被赋值的卡片，也就是魔术师已经把这张卡片拿出去了，
                        所以我们应该多循环一次，跳过这张卡片
                    */
                    if (p.data != 0){
                        i--;
                    }
                }
                if (p.data == 0){
                    p.data = cardNum;
                    cardNum++;
                }
            }
    
            return header;
        }
    
        public void printList(Node L){
            Node p = L;
            while (p.next != L){
                System.out.println(p.data);
                p = p.next;
            }
            System.out.println(p.data);
        }
        public static void main(String[] args) {
            MagicCard list = new MagicCard();
            //一共13张牌
            int num = 13;
            Node L = list.createList(num);
            list.getCard(L , num);
            list.printList(L);
        }
    }