1. 反转二叉树
解：运用递归；反转左子树，反转右子树，交换左右子树
2.反转单链表
解:
- 递归解法：
Java
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode p = head.next;
ListNode q = reverseList(p);
head.next = null;
p.next = head;
return q;
}
2. 头插法
```java```
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode p = head.next;
head.next = null; //注意此句
ListNode q;
while(p!=null){
q = p.next;
p.next = head;
head = p;
p = q;
}
return head;
}
3.通过两个栈实现一个队列
解： A栈负责装入，B栈负责取出。取出操作的时候若B栈没有元素，将A栈元素全部取出压栈入B。
4. Tencent2013 笔试题：
题目： 用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
解析：该题的直观思想是将6个数组进行全排列，然后去除不符合条件的结果。关于全排列的实现算法，大家可以参考这个链接 全排列（含递归和非递归的解法）,这里我们给出两种其他思路。
解法一：将6个节点构成3和5不连通的无向图，分别以每个节点为初始节点进行图的遍历。结果去重（可以考虑直接将遍历结果存入set结构中），然后去“4”在第三位的。
Java
public class Tencent2013 {
private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet<String> set = new TreeSet<String>();
private void run() { //构建图
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 is the 4th num, 5 is the 6th num. can not be neighbor
a[3][5] = 0;
a[5][3] = 0;
for (int i = 0; i < n; i++) {
depthFirstSearch(i);
}
//
for (String str : set) {
if (str.indexOf("4") != 2) {
System.out.println(str);
}
}
}
//深度优先遍历 graph
private void depthFirstSearch(int i) {
visited[i] = true;
result += b[i];
if (result.length() == n) {
set.add(result);
}
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
}
}
result = result.substring(0, result.length() - 1);
visited[i] = false;
}
public static void main(String[] args) {
new Tencent2013().run();
}
}
**解法二**：（思路广）
该算法的性能比较差，对于有n个数的话，循环的次数是10的n次方级，n如果比较大的话绝对不能采用该法解题。这里只是给出作为一种新颖的思路。
```Java```
//Java代码
for (int i = 122345; i <= 543221; i++) {
String sb = String.valueOf(i);
String temp = sb.replaceFirst("1", "a");
temp = temp.replaceFirst("2", "a");
temp = temp.replaceFirst("2", "a");
temp = temp.replaceFirst("3", "a");
temp = temp.replaceFirst("4", "a");
temp = temp.replaceFirst("5", "a");
if (!"aaaaaa".equals(temp)) continue;
//排除4在第三位
if (sb.indexOf("4") == 2) continue;
//3 and 5 be together
if (sb.indexOf("35") > -1 || sb.indexOf("53") > -1) continue;
System.out.println(i);
}
5.旋转字符串
给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
解：三步反转法：
- 将要旋转的部分反转
- 将剩余的部分反转
- 反转整个字符串
Java
public String reverse(String s) {
StringBuilder builder = new StringBuilder(s);
builder = builder.reverse();
return builder.toString();
}
public String moveToTail(String s, int n) {
String s1 = this.reverse(s.substring(0, n));
String s2 = this.reverse(s.substring(n));
return this.reverse(s1 + s2);
}
