面试题 08.06. 汉诺塔问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    private void move(int n, List<Integer> source, List<Integer> tmp, List<Integer> target) {
        if (n == 1) {
            Integer plate = source.remove(source.size() - 1);
            target.add(plate);
            return;
        }

        move(n - 1, source, target, tmp); // 将 source 上面的 n - 1 个盘子移动到 tmp 暂存
        Integer plate = source.remove(source.size() - 1); // 将 source 剩下的最下面的盘子移动至 target
        target.add(plate);
        move(n - 1, tmp, source, target); // 将之前暂存在 tmp 的 n - 1 个盘子移动至 target 以完成整个过程
    }
}

References

面试题 08.06. 汉诺塔问题