YuanbaoQiang
0%

老韩数据结构-Josephu问题（单向链表解法）

Posted on In Valine:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

单向链表解法

迭代解法见：LeetCode-Josephu问题（圆圈中最后剩下的数字）

约瑟夫用单链表解决比较简单，只需要定义两个指针即可，处理方法见deal()方法。除此之外详细的节点定义及构建已给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
public class Josephu2 {
    public static void main(String[] args) {
        SLL sll = new SLL(8); // 8个人
        sll.construct();
        int deal = sll.deal(3); // 每次报3下
        System.out.println(deal); // 6
    }
}


class SLL {
    int n; // 最大节点数量

    // 创建头节点，val为0
    Node first = new Node(0);


    /*
     * @description: 创建长度为n的环形链表
     * @author: YuanbaoQiang
     * @date: 2020/8/25 20:41
     * @param n 节点数量
     * @return:
     */
    public SLL(int n) {
        this.n = n;
    }


    /*
     * @description: 构建单向环形链
     * @author: YuanbaoQiang
     * @date: 2020/8/25 20:56
     * @param
     * @return: void
     */
    public void construct(){
        Node cur = first;
        for(int i = 1; i <= n; i++){
            Node node = new Node(i);
            add(node);
            cur = node;
        }
        cur.next = first;
    }


    /*
     * @description: 添加节点
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:33
     * @param node
     * @return: void
     */
    public void add(Node node){
        Node cur = first;
        while(true){
            if(cur.next == null){
                break;
            }
            cur = cur.next;
        }
        cur.next = node;
    }



    /*
     * @description: 遍历数组
     * @author: YuanbaoQiang
     * @date: 2020/8/25 20:37
     * @param
     * @return: void
     */
    public void list(){
        Node cur = first;
        while(true){
            if(cur.next == first){
                break;
            }
            System.out.printf("节点 %d\n",cur.val);
            cur = cur.next;
        }
    }


    /*
     * @description: 处理约瑟夫问题
     * @author: YuanbaoQiang
     * @date: 2020/8/25 21:03
     * @param
     * @return: void
     */
    public int deal(int m){
        // 定义两个指针 helper 和 cur
        Node cur = first;
        Node helper = cur;

        // helper 定位在 cur的前一个位置
        for(int i = 0; i < n - 1; i++){
            helper = helper.next;
        }


        while(true){
            if(helper == cur){
                break;
            }

            // cur 和 helper同时后移 m-1次
            // cur到达目标位置
            for(int i = 0; i < m - 1; i++){
                helper = helper.next;
                cur = cur.next;
            }

            helper.next = cur.next;
            cur = cur.next;
        }
        return cur.val;
    }
    
}


// 定义节点
class Node{

    Node next;
    int val;


    public Node(int val){
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}