鏈表：
無意間發(fā)現(xiàn)的一個(gè)面試總結(jié)感覺不錯(cuò)
鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是用一組任意的存儲單元（可以是連續(xù)的恤批，也可以是不連續(xù)的）存放數(shù)據(jù)元素喜庞。
鏈表中每一個(gè)元素成為“結(jié)點(diǎn)”，每一個(gè)結(jié)點(diǎn)都是由數(shù)據(jù)域和指針域組成的雷猪，每個(gè)結(jié)點(diǎn)中的指針域指向下一個(gè)結(jié)點(diǎn)。Head是“頭指針”晰房，表示鏈表的開始，用來指向第一個(gè)結(jié)點(diǎn)殊者，而最后一個(gè)指針的指針域?yàn)镹ULL(空地址)，表示鏈表的結(jié)束猖吴。
常見的基礎(chǔ)操作是插入、刪除等海蔽，詳細(xì)代碼參考
1共屈、鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)分析及代碼參考
2、鏈表的中間節(jié)點(diǎn)
分析：我們可以定義兩個(gè)指針准潭，一個(gè)每次移動(dòng)一步，另一個(gè)每次移動(dòng)兩步刑然。當(dāng)每次移動(dòng)兩步的指針指向了鏈表的尾節(jié)點(diǎn)時(shí)泼掠，每次移動(dòng)一步的指針正好處于中間位置挡逼，即我們要找的中間節(jié)點(diǎn)位置腻豌。當(dāng)然家坎，這是在不知道鏈表的長度，且為了減少時(shí)間復(fù)雜度的解法苏携。
代碼：
/*
????求鏈表的中間節(jié)點(diǎn)
*/??
pNode?getCenterPoint(pNode?head)??
{??
if?(head?==?NULL?||?head->next?==?NULL)?//如果鏈表為空做瞪，或僅有頭節(jié)點(diǎn)??
????{??
return?head;??
????}??
????pNode?pA?=?head;??
????pNode?pB?=?head;??
while(pB?!=?NULL?&&?pB->next?!=?NULL)??
????{??
????????pA?=?pA->next;??
????????pB?=?pB->next->next;????????
????}??
return?pA;??
}??
3、鏈表是否存在環(huán)
分析：判斷一個(gè)鏈表是否存在環(huán)，可以定義兩個(gè)指針装蓬，一個(gè)每次移動(dòng)一步著拭，另一個(gè)每次移動(dòng)兩步。如果每次移動(dòng)兩步的指針指向了NULL牍帚，則說明不存在環(huán)儡遮；如果兩個(gè)指針相遇，則說明存在環(huán)履羞。
代碼：
/*
????判斷鏈表是否存在環(huán)
*/??
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)??
{//?若兩個(gè)指針相遇峦萎，則存在環(huán)??
return?true;??
????????}??
????}??
return?false;??
}
4、兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)：
分析參考
5忆首、反轉(zhuǎn)鏈表：
分析參考（這個(gè)沒太理解有時(shí)間再看下）
6、輸入n個(gè)整數(shù)被环，找出其中最小的K個(gè)數(shù)
PS：補(bǔ)充點(diǎn)構(gòu)造函數(shù)知識
概念：
簡單地說糙及，vector是一個(gè)能夠存放任意類型的動(dòng)態(tài)數(shù)組，能夠增加和壓縮數(shù)據(jù)
C++ Vectors可以使用以下任意一種參數(shù)方式構(gòu)造:
vector();//1. 無參數(shù) - 構(gòu)造一個(gè)空的vector,
vector( size_type num, const TYPE &val );//2.?數(shù)量(num)和值(val) - 構(gòu)造一個(gè)初始放入num個(gè)值為val的元素的Vector?
vector( const vector &from );//?3. vector(from) - 構(gòu)造一個(gè)與vector from 相同的vector
vector( input_iterator start, input_iterator end );//?4. 迭代器(start)和迭代器(end) - 構(gòu)造一個(gè)初始值為[start,end)區(qū)間元素的Vector(注:半開區(qū)間).
vector和list的區(qū)別：
vector對于隨機(jī)訪問的速度很快筛欢，但是對于插入尤其是在頭部插入元素速度很慢浸锨，在尾部插入速度很快。list對于隨機(jī)訪問速度慢得多版姑，因?yàn)榭赡芤闅v整個(gè)鏈表才能做到柱搜，但是對于插入就快的多了，不需要拷貝和移動(dòng)數(shù)據(jù)剥险，只需要改變指針的指向就可以了聪蘸。另外對于新添加的元素，Vector采用的是從尾部追加表制，而List可以任意加入,同時(shí)可以高效的插入刪除元素健爬。list不支持隨機(jī)訪問。所以沒有?at(pos)和operator[]么介。
vector 中參數(shù)可執(zhí)行常用函數(shù)：
1.push_back ? ? ? ? ?在數(shù)組的最后添加一個(gè)數(shù)據(jù)
2.pop_back ? ? ? ? ? 去掉數(shù)組的最后一個(gè)數(shù)據(jù)?
3.at ? ? ? ? ? ? ? ? 得到編號位置的數(shù)據(jù)
4.begin ? ? ? ? ? ? ?得到數(shù)組頭的指針
5.end ? ? ? ? ? ? ? ?得到數(shù)組的最后一個(gè)單元+1的指針
6.front ? ? ? ? ? ? ?得到數(shù)組頭的引用
7.back ? ? ? ? ? ? ? 得到數(shù)組的最后一個(gè)單元的引用
8.max_size ? ? ? ? ? 得到vector最大可以是多大
9.capacity ? ? ? ? ? 當(dāng)前vector分配的大小
10.size ? ? ? ? ? ?當(dāng)前使用數(shù)據(jù)的大小
11.resize ? ? ? ? ?改變當(dāng)前使用數(shù)據(jù)的大小娜遵，如果它比當(dāng)前使用的大，者填充默認(rèn)值12.reserve ? ? ? 改變當(dāng)前vecotr所分配空間的大小
13.erase ? ? ? ? ?刪除指針指向的數(shù)據(jù)項(xiàng)
14.clear ? ? ? ? ? 清空當(dāng)前的vector
15.rbegin ? ? ? ? 將vector反轉(zhuǎn)后的開始指針返回(其實(shí)就是原來的end-1)
16.rend ? ? ? ? ? 將vector反轉(zhuǎn)構(gòu)的結(jié)束指針返回(其實(shí)就是原來的begin-1)
17.empty ? ? ? ? 判斷vector是否為空
18.swap ? ? ? ? ?與另一個(gè)vector交換數(shù)據(jù)??
回到題目（輸入n個(gè)整數(shù)壤短，找出其中最小的K個(gè)數(shù)）分析主要做個(gè)排序然后取出最小的k個(gè)數(shù)就可以了设拟，參考代碼
好奇時(shí)間復(fù)雜度怎么算出來的可以看看這塊
比如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次
}
最后總的次數(shù)為
1+（n+1）+n+n+1+1=3n+3
所以時(shí)間復(fù)雜度f（o）=n；（時(shí)間復(fù)雜度只管n的最高次方久脯，不管他的系數(shù)和表達(dá)式中的常量）不過要注意時(shí)間復(fù)雜度的f(x)在有限次時(shí)就用具體數(shù)值表示纳胧，無限次時(shí)就用n，n的平方桶现，log以2為底n的對數(shù)躲雅，其實(shí)很簡單就是看n的最高次方，看n的最高次方等于幾,f(x)就等于幾骡和。
二分法：
首先說一下二分法排序的原理相赁，算法思想簡單描述：?
1相寇、將low=0,值為1；high=9钮科，值為10(因?yàn)閿?shù)組下標(biāo)從0開始)唤衫；mid=(low+high)/2
2、將mid的值與查找的數(shù)作比較绵脯，如果mid<n佳励，即n在mid的右邊，所以左邊界變?yōu)閘ow = mid+1蛆挫，相反如果mid>n赃承，即n在mid的左邊，即右邊界要變成high=mid-1
常見面試?yán)?a target="_blank" rel="nofollow">參考
感覺自己數(shù)學(xué)思想欠缺悴侵，這種題最好的辦法是先據(jù)幾個(gè)數(shù)（1瞧剖、2、多）基本上算法思想就出來了可免，然后可以嘗試些偽代碼抓于，再詳細(xì)點(diǎn)是代碼具體函數(shù)
