1.链表的翻转
思路：
原地算法： 不借助外在的存储空间，首先使用头插法，在链表的头部插入节点，每一轮循环插入一个节
class Node( int data; Node next; ) public void test(Node head){ Node temp = null; Node nextnode = null; while(head != null){ nextnode = head.next; head.next = temp; temp = head; head = nextnode; } }借助外部结构： 使用栈来实现链表的翻转
public void test(Node head){ Stack stack = new Stack(); while(head != null){ stack.push(head.data); head = head.next; } while(!stack.isEmpty()){ System.out.println(stack.pop()); } }2.判断链表是否有环,以及环的入口
思路：
使用Floyed算法来判断链表时候有环，即使用两个指针，以不同的速度前进，如果链表没有环，则两个指针不会相遇，如果有，则会在某一个时刻相遇
public Boolean test(Node head){ Node head1 = head ; Node head2 = head; while(head != null){ head1 = head.next; head2 = head.next.next; if(head1 == head2) return true; } return false; }思路：
对于环的入口，首先我们设置两各指针，一个快（兔子）一个慢（乌龟），假设当兔子和乌龟在环里相遇，则这个时候，兔子已经在环内跑了n圈，每圈的长度为L,假设乌龟在进行环之前跑了k的路，进入环之后，跑了x之后与兔子相遇，所以等式： 2（k + x) = k + nL + x => k + x = nL.
故： 乌龟从起点跑到循环入口的距离为： nL - x
又：此时将兔子的速度和乌龟一样，则兔子在圈内跑n-1圈之后，又会回到和乌龟相遇的点，只要在跑L-x的路，就可以回到下一轮循环的起点.
即：（n-1)L + (L-x) = nL - x
int FindLoop(Node head){ Node slow = head; Node fast = head; int loopExists = 0,count =0; while(slow && fast && fast.next){ slow = slow.next; fast = fast.next.next; if(slow == fast ){ loopExists = 1; break; } } if(loopExists){ fast = fast.next; while(slow != fast){ fast = fast.next; couter++; } return counter; } return 0; //不存在环 }3.栈来模拟队列
思路：
队列的特性是FIFO,栈的特性是FILO,因此使用栈来模拟队列，则使用两个栈来运行，栈1，栈2，当进行入队操作时，则往栈1中push元素，当进行出队的时候，将栈1中的元素出栈并压栈到栈2中，然后进行出栈操作，在完后的出队是，需要注意的是，先要判断栈2中时候有元素，若有有，则从栈2出栈，没有的话，则将栈1的元素出栈然后压栈到栈2，在进行出栈.
public void line(){ Stack stack1,stack2; //入队 public void enqueue(int data){ stack1.push(data); } public void dequeue(){ if(!stack2.isEmpty()){ stack2.pop(); }else{ if(!stack1.isEmpty()){ while(!stack1.isEmpyt()){ stack2.push(stack.pop()); } stack2.pop(); }else{ return null; } } } }4.使用队列模拟栈
思路:
栈的特性是FILO,队列的特性是FIFO,使用；两个队列q1,q2， 当进行压栈操作时，对q1执行入队操作，当进行出栈操作时，首先将q1中前n-1个元素出队并入队到q2中，然后将q1中的元素出队，注意必须保证一个队列是空的，当进行压栈的时候，对有数据的队列进行入队。
public void test(){ Queue queue1 ,queue2; static count = 0; public void push(int data){ queue1.queue(data); count ++; } public void pop(){ if(count == 0 ){ ; }else if(count == 1){ queue1.deque(); count--; }else{ while(count > 1){ queue2.queue(queue1.deque()); count--； } queue1.deuque(); switch(queue1,queue2); } } }5.树的前序,中序遍历
思路：（非递归）
使用栈的数据结构来进行树的输出
class Node { int value; Node left; Node right; } 前序 public void print(Node root){ Stack<Node> stack = new Stack<Node>(); while(1){ while(root!= null){ System.out.println(root.value); stack.push(root); root = root.left; } if(stack.isEmpty() == null) break; root = stack.pop(); root = root.rigth; } } 中序 public void print2(Node root){ Stack<Node> stack = new Stack<Node>(); while(1){ while(root != null){ stack.push(root); root = root.left; } if(stack.isEmpty == null) break; root = stack.pop(); System.out.println(root.value); root = root.right; } }6.分层遍历
思路：
使用队列存储节点
public void print3(Node root){ Queue<Node> Que = new Queue<Node>(); Que.queue(root); Node temp = null; while(!Que.isEmpyt()){ temp = Que.Deque(); System.out.println(temp.value); if(temp.left != null) Que.queue(temp.left); if(temp.right != null) Que.queue(temp.right); } }7.从遍历顺序遍历二叉树
思路：
使用队列和栈
public void print4(Node root){ Stack<Node> Sta = new Stack<Node> (); Queue<Node> Que = new Queue<Node> (); Que.queue(root); Node temp = null; while(!Que.isEmpyt()){ temp = Que.Deque(); Stack.push(temp); if(temp.right != null) Que.queue(temp.right); if(temp.left != null) Que.queue(temp.left); } while(!Sta.isEmpty()) System.out.println(Sta.pop()); }8.曲折遍历二叉树
思路：
使用两个栈解决问题
public void ZigZag(Node root){ Node temp; int leftToRight = 1; if(root == null) return; Stack CurrentLevel = new Stack(); Stack NextLevel = new Stack(); CurrentLevel.push(root); while(!CurrentLevel.isEmpty()){ temp = CurrentLevel.pop(); if(temp != null){ System.out.println(temp.value); if(leftToRight == 1 ){ if(temp.left != null) NextLevel.push(temp.left); if(temp.right != null) NextLevel.push(temp.right); }else{ if(temp.right != null) NextLevel.push(temp.right); if(tmep.left != null) NextLevel.push(temp.left); } } if(CurrentLevel.isEmpty()){ leftToRight = 1- leftToRight; swap(CurrentLevel,NextLevel); } } }9.线索二叉树的后继节点和前驱节点
思路：
为了节省每个Node节点的空间，引出线索二叉树，即每个Node有一个前驱节点，又有一个后继节点，根据不同的遍历方式，其前驱节点和后继节点也不同，
class Node{ int Value; int tagleft; int tagrihgt; Node left; Node right; }当tagleft,tagright为0时，表示没有前驱或后继节点，则left,right则分别指向其指定遍历顺序的前驱和后继节点.
10.二叉搜索树的节点的插入
思路：
如果没有指定插入的位置，则将新的节点插入到空闲位置，
如果有指定插入的位置，则进行比较，然后插入到合适的位置.
//没有任何插入约束 public void insert(Node root, Node value){ Node node = new Node(vlaue); node.left = node.rihgt = null; Queue Que = new Queue(); Que.queue(root); Node temp = null; if(!Que.isEmpty()){ tmep = Que.Deuqe(); if(temp.left == null){ temp.left = node; break; }else{ Que.queue(temp.left); } if(temp.right == null){ temp.right = node; break; }else{ Que.queue(temp.right); } } } //将元素插入到二叉查找树中 public void insert(Node root,Node value){ Node node = new Node(value); Queue Que = new Queue(); Que.queue(root); Node temp = null; while(!Que.isEmpty()){ temp = Queue.Deque(); if(temp.value > node.value){ if(temp.left == null){ temp.left = node; }else{ Que.queue(temp.left); } }else{ if(temp.right == null){ temp.right = node; }else{ Que.queue(temp.right); } }else{ System.out.println(“已存在”); break; } } }11.二叉搜索树删除节点
思路：
对于二叉树的节点，分3中情况：
当被删除的节点是叶子节点，则将其父节点的左右指针变为NULL;
当被删除的节点有一个子节点，则找出删除节点的父节点,把子节点直接设置成父节点的子节点；
当被删除的节点有两个子节点，则在左子树中找到数值最大的那个节点，并用它的键来替换删除节点的键.然后对失去的节点运行满足条件的规则.
12.平衡二叉树的平衡问题
思路：
平衡二叉树是一种为了防止单节点二叉树的查找问题，即二叉树中每层只有一个节点，这样在查找的的复杂度比较高，因为引出平衡二叉树，节点的左子树和右子树的高度之差小于等于1.
只需要把首个失去平衡的节点修复好之后，AVL树性质都会自动回复，我们把需要恢复平衡的节点记为X，因为有以下几种情况：
当向X的左侧节点的左子树插入元素，LL旋转
public void rotatell(Node x){ Node w = x.left; x.left = w.right; w.right = x; x.height = max(height(x.left),height(x.right)) + 1; w.height = max(height(w.left),height(w.right)) + 1; } 2. 当向X的右侧节点的右子树插入元素，RR旋转 public void rotaterr(Node x){ Node w = x.right; x.right = w.left; w.left = x; x.height = max(height(x.left),height(x.right)) + 1; w.height = max(height(w.left),height(w.right)) + 1; }当向X的左侧子节点的右子树插入元素，即LR旋转,需要旋转两次
public void rotate(Node z ){ z.left = rotaterr(z.left); rotatell(z.left); }当向X的右侧子节点的左子树插入元素，即RL旋转，需要旋转两次
public void rotate(Node z){ z.right = rotatell(z.right); rotate(z.right); }13.堆化
思路：
堆：即节点要么大于子节点(大根堆),要么小于子节点(小根堆),可用于排序
堆的存储可以使用数组进行存储：
class head{ int count; int capacity; int heap_type; int [] array; }堆化：向下渗透
void down(head h,int i){ int l,r,max,temp; l = leftChild(h,i); r = rightChild(h,i); if(l != -1 && h.array[l] > h.array[i]){ max = l; }else{ max = i; } if(r != -1 && h.array[r] > h.array[max]){ max = r; } if(max != i){ temp = h.array[i]; h.array[i] = h.array[max]; h.array[max] = temp; down(h.max); } }插入元素： 向上渗透
将新元素放入到堆的末尾，
自下而上的执行堆化，直至到达根节点为止.
public int insert(head h,int data){ if(h.count == h.capacity) resizeHead(h)； int i= h.count++; while( i> 1 && data > h.array[(i-1)/2]){ h.array[i] = h.array[(i-1)/2]; i = (i-1)/2; } h.array[i] = data; }删除元素：
只需要删除掉根元素，这是标准（最大）二叉堆所需支持的唯一一种删除操作，删除根元素后，把数组里的最后一个元素复制到0号位置,也就是复制到根所在的位置.
public int delete(head h){ int data; if(h.count == 0) return -1; data = h.array[0]; h.array[0] = h.array[h.count-1]; h.count--; down(h,0); return data; }14.排序
14.1冒泡排序
public void sort(int[] array,int n){ for(int i = 0 ;i<n ;i++){ for(int j = 1; j < n ; j++){ int temp; if(array[i] < array[j]){ temp = array[i]; array[i] = array[j]; array[j] = temp; } } } }14.2选择排序
public void sort(int [] array,int n){ int min,temp; for(int i = 0 ; i< n -1 ; i++){ min = i; for(int j = i+1; j< n ;j++){ if(array[j] < array[min]) min = j; } temp = array[min]; array[min] = array[i]; array[i] = temp; } }14.3插入排序
public void sort(int [] array,int n){ for(int i = 1 ;i< n ;i++){ int temp = array[i]; int j = i; while(array[i-1] > temp && j >= 1){ array[i] = array[i+1]; j--; } array[j] = temp; } }14.4希尔排序(递减增量排序)
public void sort(int [] arrray, int n){ for(int h = 1; h < n /3 ; h = 3*h+1); for(; h > 0 ; h = h/3){ for(int i = h; i < n-1;i +=1){ v = array[i]; j = i; while(j >= h && array[j-h] > v){ array[j] = array[j-h]; j-=h; } array[j] = v; } } }14.5快速排序
public void sort(int[] array,int low,int length){ int pivot; if(hight > low){ pivot = Partition(array,low,hight); sort（array,low,pivot-1); sort(arrry,pivot+1,hight); } } public int Partition(int[] array,int low, int high){ int left,right,pivot_item = array[low]; left = low; right = high; while(left < right){ while(array[left] <= pivot_item) left++; while(array[right] >= privot_item) right--; if(left < right) swap(array,left,right); } array[low] = array[right]; array[right] = pivot_item; return right; }14.6堆排序
public void sort(int[] array,int n){ Head head = new Head(); int old_size ,i ,temp; buildHead(head,array,n); old_size = head.count; for(int i = n-1 ; i>0 ; i++){ temp = head.array[0]; head.array[0] = head.array[head.count-1]; (head.array[head.count-1]) = temp; head.count--; down(head,0); } head.count = old_size; }14.7计数排序
public void sort(int[] X,int n ,int[] Y,int K){ int [] Z = new int [K],i,j; for(int i = 0;i< K,i++) Z[i] = 0; for(int j = 0;j<n;j++) Z[X[j]] = Z[X[j]] + 1; for(int i = 1; i< K; i++) Z[i] = Z[i] + Z[i-1]; for(int j = n-1;j>=0;j--){ Y[Z[X[j]]-1] = X[j]; Z[X[j]] = Z[X[j]]-1; } }