36.两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
拿到这个题，试想一下，如果两个链表的长度一样，应该怎么做，当然就是两个链表从头结点开始同时往后遍历，找到第一个相同的结点即可。
那么上升到更一般的情况下，两个链表长度不相等，应该怎么做，单向链表是不可逆的，因此我们没法从后往前找第一个公共结点。我们可以仿照两个链表长度相同到的情况下进行求解，怎么让两个链表长度相同呢，就是分别求出两个链表的长度，然后让长的那个链表先往后走两个链表之间的差值的长度即可。
代码如下
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null){
return null;
}
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
//用两个数字分别记录两个链表的长度
int cnt1 = 0,cnt2 = 0;
while(cur1!=null){
cnt1++;
cur1 = cur1.next;
}
while(cur2!=null){
cnt2++;
cur2 = cur2.next;
}
cur1 = pHead1;
cur2 = pHead2;
//如果链表1长，就让链表1走cnt1-cnt2的长度
//如果链表2长，就让链表2走cnt2-cnt1的长度
int cnt = 0;
if(cnt1<cnt2){
while(cnt<cnt2-cnt1){
cur2 = cur2.next;
cnt++;
}
}else{
while(cnt<cnt1-cnt2){
cur1 = cur1.next;
cnt++;
}
}
//两个链表的指针同时向后走，碰到第一个相等的结点就是第一个公共结点
while(cur1!=null&&cur2!=null){
if(cur1==cur2){
return cur1;
}else{
cur1 = cur1.next;
cur2 = cur2.next;
}
}
return null;
}
}
37.数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
最简单直观的方法当然是按顺序统计，这样的时间复杂度是O(n)
代码如下
public class Solution {
//private int cnt = 0;
public int GetNumberOfK(int [] array , int k) {
if(array.length<=0){
return 0;
}
int cnt = 0;
for(int num:array){
cnt = num==k?cnt+1:cnt;
}
return cnt;
}
}
但是既然题目中已经给了排序这个信息，我们就应该利用好排序这个信息，即用BinarySearch进行寻找第一个K出现的位置和第一个大于K的数出现的位置。
在使用二分查找的时候，我们需要明白几点：
1.二分查找的原理就是"逼近"，当mid指向的数大于等于target时，证明target在前半段数组中；反之target在后半段数组中,直到低位指针与高位指针重合；
2.如果我们要找的数不在数组中，可能存在两种情况
1.target夹在数组中间，例如target=4,array={1,3,5,7,9}；这种情况下试想，
我们通过逼近的方法可以“知道”4在3的后面，而7,9显然是大于4的，所以最后夹在中间的只有5
这里可以延伸为我们在数组中寻找target时，如果target不存在，则会找到第一个大于target的数；
2.target大于数组中全部的数，例如target=6，array={1,2,3,4,5}，
我们最好在写代码的时候就将high定义为array.length，这样通过逼近的方法，最后l和h重叠的时候就出界了，这样方便判断；
根据以上可以写出如下流程的代码
1.对target进行二分查找，找到target出现的第一个位置；
2.对target+1进行二分查找，这里的意思是找到第一个大于等于target+1的元素，类似于放缩发也就找到了第一个大于target的元素；
3.对l进行判断是不是上面提到的两种不存在的情况，对于第一种情况需要判断array[first]和k是否相等，对于第二种情况需要判断first是否出界了，满足以上两者之一的，都需要判定target不存在数组中，返回0.
代码如下
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length<=0){
return 0;
}
//对k进行二分查找，找到k第一次出现的位置
int first = binarysearch(array,k);
//对k+1进行二分查找，找到大于等于K+1的数，即大于K的数第一次出现的位置；
int last = binarysearch(array,k+1);
//满足target夹在数组中某两个数中间或target大于数组中全部数情况之一的，需要返回0
return (first==array.length||array[first]!=k)?0:last-first;
}
//定义简单二分查找函数
private int binarysearch(int [] array,int k){
int l = 0,h = array.length;
while(l<h){
int m = (l+h)/2;
if(array[m]>=k){
h = m;
}else{
l = m+1;
}
}
return l;
}
}
二叉树的深度
输入一棵二叉树，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
这个题思路倒是简单，就用一个变量来保存当前最大深度，
然后用深度遍历的方法统计各条路线的长度，然后与这个最大深度进行比较取大者，最后输出最大值。
代码如下
public class Solution {
private int depth = 0;
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
//这里要注意不要采坑！！！
//我们往下进行递归的时候会使计数+1
//以单个根节点为例，左右结点为空，但是计数+1了，层数为0+1=1,这才是符合实际情况到的
//所以在入口的时候传递的初始层数应该为0
find_depth(root,0);
return depth;
}
//对二叉树进行深度遍历
public void find_depth(TreeNode root,int cnt){
//当递归到结点为null的时候，将当前的cnt与depth进行比较取大者
if(root==null){
depth = cnt>depth?cnt:depth;
return;
}
//对左右子树进行递归处理
find_depth(root.left,cnt+1);
find_depth(root.right,cnt+1);
}
}
39.平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
这个题的思路还是判断左右子树的高度差是否小于1，我们可以采用这样的方式，即初始化一个布尔变量为true,全局中只要出现一个位置不满足平衡二叉树的条件，就会使这个变量被赋值为false，如果全局都满足平衡二叉树，最后的输出也就是true;同时，在计算树的深度的时候要学会通过递归返回值，具体步骤如下
1.初始化一个全局布尔变量boolean res = true；
2.构建一个整型返回值的函数用来计算树的高度，注意这个函数既承担了在递归中不断计算树的深度的任务，又承担着判断各子树是否为平衡二叉树，当然只要判定一次不为平衡二叉树，其它也就无所谓了。
有了这个思路，代码如下
public class Solution {
//初始化一个全局布尔变量
private boolean res = true;
public boolean IsBalanced_Solution(TreeNode root) {
//height函数无需返回值，因为只需要在当中判定res是否会变成false即可
height(root);
return res;
}
private int height(TreeNode root){
//如果结点为空则返回0，这既是对根节点的判定，也是一个递归计算深度的初始值
if(root==null){
return 0;
}
//对左右子树进行递归
int left = height(root.left);
int right = height(root.right);
if(Math.abs(left-right)>1){
res = false;
}
//这里承担着一层层往上递归树的深度的任务
//可以这样看，root的深度是多少？是1加上左子树的深度和右子树的深度中的大者
//那么左子树深度left和右子树深度right是多少呢？
//就是又要用到这个height函数来求解了，left = height(root.left);right=height(root.right);
//当递归到叶子结点的时候，可以看到左右都为null，即叶子结点的深度为1，这也是一层层往上递归的
return 1+Math.max(left,right);
}
}
40.数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
之前做的简单难度的是找出一个只出现一次的数字，这次要找两个，要学会将复杂问题拆分成简单的子问题来求解，如果我们能根据某些特征将这些数字分成两组，第一组只包含第一个数，第二组只包含第二个数，然后再用只出现一次的一个数这个思路来求解不就行了吗？
假设这两个只出现一次的数为a,b我们对数组中所有的数求异或，最后得到的结果就是a^b，异或异或顾明思意这个结果肯定会包含1，因为a,b肯定是不相等，我们找到第一个为1的位，例如00100这个数，整个数组就被划分成两个部分了，1.该位为1；2该位不为1；
该位为1的数与上00100肯定不为0,该位为0的数与上00100肯定为0
按照这个思路，流程如下
1.求出这两个数相异或的结果
2.求出这个结果中第一位为1的这个数
3.根据这个判定条件，分别不同条件下的数不断求异或运算，得到最终的两个数
代码如下
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int diff = 0;
for(int num:array){
diff ^= num;
}
//找到第一个不为1的数
//负数的二进制是取反加1
//以diff=10100为例，-diff = 01011+1=01100
//10100&01100=00100，正好就是我要求的
diff &= -diff;
for(int num:array){
//这里就是分为了两个元素区，第一个为在该位上为0，则与diff后全部为0,我们异或所有的这些数即可
//相反得到到的就是另外一个数
if((num&diff)==0){
num1[0] ^=num;
}else{
num2[0] ^=num;
}
}
}
}
