学习笔记C++（链表、二分法--常见面试题分析）
链表：
链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。
链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。
常见的基础操作是插入、删除等，详细代码参考
1、链表中倒数第k个结点分析及代码参考
2、链表的中间节点
分析：我们可以定义两个指针，一个每次移动一步，另一个每次移动两步。当每次移动两步的指针指向了链表的尾节点时，每次移动一步的指针正好处于中间位置，即我们要找的中间节点位置。当然，这是在不知道链表的长度，且为了减少时间复杂度的解法。
代码：
/*
求链表的中间节点
*/
pNode getCenterPoint(pNode head)
{
if (head == NULL || head->next == NULL) //如果链表为空，或仅有头节点
{
return head;
}
pNode pA = head;
pNode pB = head;
while(pB != NULL && pB->next != NULL)
{
pA = pA->next;
pB = pB->next->next;
}
return pA;
}
3、链表是否存在环
分析：判断一个链表是否存在环，可以定义两个指针，一个每次移动一步，另一个每次移动两步。如果每次移动两步的指针指向了NULL，则说明不存在环；如果两个指针相遇，则说明存在环。
代码：
/*
判断链表是否存在环
*/
bool isExitCycle(pNode head)
{
if(head == NULL)
{
return false;
}
pNode pA = head;
pNode pB = head;
while(pB->next != NULL && pB != NULL)
{
pB = pB->next->next;
pA = pA->next;
if(pA == pB)
{// 若两个指针相遇，则存在环
return true;
}
}
return false;
}
4、两个链表的第一个公共结点：
分析参考
5、反转链表：
分析参考（这个没太理解有时间再看下）
6、输入n个整数，找出其中最小的K个数
PS：补充点构造函数知识
概念：
简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据
C++ Vectors可以使用以下任意一种参数方式构造:
vector();//1. 无参数 - 构造一个空的vector,
vector( size_type num, const TYPE &val );//2. 数量(num)和值(val) - 构造一个初始放入num个值为val的元素的Vector
vector( const vector &from );// 3. vector(from) - 构造一个与vector from 相同的vector
vector( input_iterator start, input_iterator end );// 4. 迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
vector和list的区别：
vector对于随机访问的速度很快，但是对于插入尤其是在头部插入元素速度很慢，在尾部插入速度很快。list对于随机访问速度慢得多，因为可能要遍历整个链表才能做到，但是对于插入就快的多了，不需要拷贝和移动数据，只需要改变指针的指向就可以了。另外对于新添加的元素，Vector采用的是从尾部追加，而List可以任意加入,同时可以高效的插入删除元素。list不支持随机访问。所以没有 at(pos)和operator[]。
vector 中参数可执行常用函数：
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6.front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据
回到题目（输入n个整数，找出其中最小的K个数）分析主要做个排序然后取出最小的k个数就可以了，参考代码
好奇时间复杂度怎么算出来的可以看看这块
比如1题：
Sum1( int n )
{ int p=1, sum=0, m ; //1次
for (m=1; m<=n; m++) //n+1次
{ p*=m ; //n次
sum+=p ; } //n次
return (sum) ; //1次
}
最后总的次数为
1+（n+1）+n+n+1+1=3n+3
所以时间复杂度f（o）=n；（时间复杂度只管n的最高次方，不管他的系数和表达式中的常量）不过要注意时间复杂度的f(x)在有限次时就用具体数值表示，无限次时就用n，n的平方，log以2为底n的对数，其实很简单就是看n的最高次方，看n的最高次方等于几,f(x)就等于几。
二分法：
首先说一下二分法排序的原理，算法思想简单描述：
1、将low=0,值为1；high=9，值为10(因为数组下标从0开始)；mid=(low+high)/2
2、将mid的值与查找的数作比较，如果mid<n，即n在mid的右边，所以左边界变为low = mid+1，相反如果mid>n，即n在mid的左边，即右边界要变成high=mid-1
常见面试例子参考
感觉自己数学思想欠缺，这种题最好的办法是先据几个数（1、2、多）基本上算法思想就出来了，然后可以尝试些伪代码，再详细点是代码具体函数
