最近面试某互联网大厂。第一道题是链表反序。so easy。第二道题直接整了一个汉诺塔。我虽然知道原理，但是TMD代码不会写。下来仔细想了想，发现也不难。

总结思想就是递归，然后把大问题慢慢分解成小问题。参数inner的作用是把N层之上的塔先放到inner上，然后把N层放到to上。最后把inner上的塔借助from放到to上。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 汉诺塔是一个有3个柱的list数组。一个list表示一个柱，list从前到后的顺序表示柱从下到上的顺序
// 元素值表示在此位置的圆盘大小
class Solution {
  static int n;
  static List<Integer>[] tower = new ArrayList[3];
  public static void main(String[] args) {
    for (int i = 0; i < 3; ++i) {
      tower[i] = new ArrayList<>();
    }

    n = 4;

    for (int i = 0; i < n; ++i) {
      tower[0].add(n - i);
    }
    printTower(tower, n);

    recursion(n, 0, 1, 2);
  }

  public static void recursion(int curN, int from, int inner, int to) {
    if (curN == 1) {
      tower[from].remove(tower[from].size() - 1);
      tower[to].add(curN);
      printTower(tower, n);
    } else {
      recursion(curN - 1, from, to, inner);
      tower[from].remove(tower[from].size() - 1);
      tower[to].add(curN);
      printTower(tower, n);
      recursion(curN - 1, inner, from, to);
    }
  }

  public static void printTower(List<Integer>[] tower, int n) {
    int t0Size = tower[0].size();
    int t1Size = tower[1].size();
    int t2Size = tower[2].size();
    for (int i = n - 1; i > -1; --i) {
      String s1 = i < t0Size ? String.join("", Collections.nCopies(tower[0].get(i), "*")) : "-";
      String s2 = i < t1Size ? String.join("", Collections.nCopies(tower[1].get(i), "*")) : "-";
      String s3 = i < t2Size ? String.join("", Collections.nCopies(tower[2].get(i), "*")) : "-";
      System.out.printf("%-10s %-10s %-10s", s1, s2, s3);
      System.out.println();
    }
    System.out.println(String.join("", Collections.nCopies(30, "#")));
  }
}