1.两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思路：如果两个链表有公共节点，那么从公共节点后面开始，应该都是一样的。如果链表一比链表二长，那长的也是不相等的部分。因此我们首先求出两个链表的长度，然后让长的链表先走num步（二者长度的差距），之后让二者一起走。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int len1=GetLen(pHead1);
        int len2=GetLen(pHead2);
        int num=len1-len2;//假设1比2长
        ListNode *pLong=pHead1;
        ListNode *pShort=pHead2;
        if(len1<len2)
        {
            num=len2-len1;
            pLong=pHead2;
            pShort=pHead1;
        }
        for(int i=0;i<num;i++)
        {
            pLong=pLong->next;//长链表先走n步
        }
        while((pLong!=nullptr)&&(pShort!=nullptr)&&(pLong->val!=pShort->val))
        {
            pLong=pLong->next;
            pShort=pShort->next;
        }
        return pLong;

    }
    int GetLen(ListNode* Head)//求链表长度的函数
    {
        int len=0;
        ListNode *p=Head;
        while(p!=nullptr)
        {
            len++;
            p=p->next;
        }
        return len;
    }
};

2.统计一个数字在排序数组中出现的次数
思路：二分查找。

class Solution {
public:
    int binary(vector<int> data,int low,int high,int k)
        {
            int m;
            while(low<=high)
            {
                m=(high+low)/2;
                if(data[m]==k) return m;
                else if(data[m]<k) low=m+1;//小于说明k在m右面
                else high=m-1;//大于说明k在m左面            
            }
            return -1;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        //使用二分查找，找出数据，然后进行左右进行统计
        int len=data.size();
        if(len==0) return 0;
        int m=binary(data,0,len-1,k);//找到k的位置
        if(m==-1) return 0;//没有k
        int left=m-1;
        int right=m+1;
        int count=1;
        while(left>=0&&data[left]==k)//左查
        {
            left--;
            count++;
        }
        while(right<len&&data[right]==k)//右查
        {
            right++;
            count++;
        }
        return count;
    }
};

3.二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路：递归左右子树，找最深的地方，加1（根节点）即为结果。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr) return 0;
        int count=0;
        int left=TreeDepth(pRoot->left);
        int right=TreeDepth(pRoot->right);
        count=(left>right)?left+1:right+1;
        return count;
    }
};

4.平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树。
思路：（1）可以沿用上一题的思路，递归寻找左右子树的深度，如果差的绝对值大于1，就返回false。（2）用后序遍历的方式遍历二叉树的每个节点，在遍历每个节点的时候记录它的深度，就可以判断是不是平衡的。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth=0;
        return IsBalanced(pRoot,&depth);
    }
    bool IsBalanced(TreeNode* pRoot,int* pDepth)
    {
        //采用了后序遍历
        if(pRoot==nullptr)
        {
            *pDepth=0;
            return true;
        }
        int left,right;
        if(IsBalanced(pRoot->left,&left)&&IsBalanced(pRoot->right,&right))
        {
            if(abs(left-right)<=1)
            {
                *pDepth=1+(left>right?left:right);//记录深度
                return true;
            }
        }
        return false;
    }
};

5.数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
注意（num&1）要加括号

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
      /*先考虑简化问题，如只有一个数字除外，则一次异或数组就可得到答案，本题有两个数字，因此考虑
        变成两个简化问题。
        在结果数字中找到第一个为1的位的位置，记为第N位。以第N位是不是1为标准把原数组中的数字分成
        两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0 。
        现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其它数字都
        出现了两次。因此到此为止，所有的问题我们都已经解决。*/
        int len=data.size();
        if(len<2) return;
        int temp=data[0];
        for(int i=1;i<len;i++)
            temp^=data[i];
        int index=findFirstBitIs(temp);//找异或得到的数的第一个为1的位置
        *num1=0,*num2=0;
        for(int i=0;i<len;i++)
        {
            if(isBit(data[i],index)==0)
                *num1^=data[i];//记录第N位都是0的
            else
                *num2^=data[i];//记录第N为都是1的
        }         
    }
     int findFirstBitIs(int num)//找第一个为1的位的位置
    {
       int indexBit = 0;
       while(((num & 1)==0) && (indexBit)<32)//如果按位与1得0，就右移一位,注意此处（num&1）要加括号
       {
           num = num >> 1;
           ++indexBit;
       }
       return indexBit;//得到从右到左第一个为1的位置
   }
     bool isBit(int num,int indexBit)
    {
       num = num >> indexBit;
       return (num & 1) == 1;//右移index位，和1与，要么相等要么不等
   }
};