鏈表的特性

鏈表由節(jié)點(diǎn)構(gòu)成雁社，節(jié)點(diǎn)=數(shù)據(jù)域+指向下一個(gè)節(jié)點(diǎn)內(nèi)存地址的指針域構(gòu)成带迟。

物理上存儲(chǔ)非連續(xù)演熟，數(shù)據(jù)結(jié)構(gòu)的邏輯順序通過指針實(shí)現(xiàn)帮哈。它在循環(huán)遍歷和查找時(shí)效率不高，但插入和刪除時(shí)間復(fù)雜度可達(dá)到O(1)馅扣。

優(yōu)點(diǎn)：建立時(shí)無(wú)需預(yù)先分配儲(chǔ)存空間斟赚，插入刪除時(shí)無(wú)需移動(dòng)大量數(shù)據(jù)。

單鏈表常用操作

1差油、創(chuàng)建拗军、插入和刪除

前插創(chuàng)建：malloc指針pInsert，pInsert->next指向pHead->next蓄喇；pHead->next指向pInsert

尾插創(chuàng)建：pTail用于保存鏈表尾指針发侵，初始pTail = L（L->next = NULL），循環(huán)插入新節(jié)點(diǎn)：malloc新節(jié)點(diǎn)pInsert妆偏，pTail->next = pInsert刃鳄，pTail = pInsert，循環(huán)結(jié)束后pTail->next置為NULL楼眷。

在第i個(gè)節(jié)點(diǎn)插入：定義pPre前驅(qū)節(jié)點(diǎn)铲汪，循環(huán)i - 1次pPre = pPre->next后熊尉，pInsert->next = pPre->next，pPre->next =?pInsert掌腰。

刪除值為x的節(jié)點(diǎn)：定義pPre前驅(qū)節(jié)點(diǎn)和pDelete要?jiǎng)h除的節(jié)點(diǎn)狰住，循環(huán)p-data != x賦值pPre = p，p = p->next齿梁，結(jié)束后前驅(qū)節(jié)點(diǎn)直接指向要?jiǎng)h除節(jié)點(diǎn)的next：pPre->next = pDelete->next

2催植、求節(jié)點(diǎn)個(gè)數(shù)（鏈表長(zhǎng)度），復(fù)雜度O(n)

判斷pHead != NULL不是空鏈表勺择；

定義長(zhǎng)度length = 0创南、pCurrent = pHead；

while條件pCurrent != NULL省核，循環(huán)pCurrent = pCurrent->next稿辙，length++；

return length气忠。

3邻储、單鏈表反轉(zhuǎn)，復(fù)雜度O(n)

判斷pHead != NULL不是空鏈表旧噪，否則直接返回原空鏈表頭指針吨娜；

定義反轉(zhuǎn)后的新鏈表頭指針pNewHead = NULL，pCurrent = pHead淘钟；

while條件pCurrent != NULL宦赠，循環(huán)：pTemp存起當(dāng)前節(jié)點(diǎn)指針，當(dāng)前節(jié)點(diǎn)指針pCurrent替換成下一個(gè)節(jié)點(diǎn)的指針pCurrent->next米母，pTemp的next指向pNewHead勾扭，pTemp賦值給pNewHead。（即铁瞒，每一次循環(huán)都是1尺借、將當(dāng)前節(jié)點(diǎn)指向下一節(jié)點(diǎn)；2精拟、新頭節(jié)點(diǎn)的next指向舊頭節(jié)點(diǎn)；3虱歪、新鏈表的頭節(jié)點(diǎn)永遠(yuǎn)指向當(dāng)前節(jié)點(diǎn)）

4蜂绎、查找倒數(shù)第K個(gè)節(jié)點(diǎn)，復(fù)雜度O(n)

?原理：一前一后兩個(gè)指針笋鄙，ahead师枣，behind，ahead先走到第K個(gè)節(jié)點(diǎn)與behind造成K個(gè)節(jié)點(diǎn)的差值萧落，之后同時(shí)移動(dòng)直到ahead->next = NULL践美，返回behind即倒數(shù)第K個(gè)節(jié)點(diǎn)

同理可查找鏈表的中間節(jié)點(diǎn)（前指針走兩步洗贰，后指針走一步，得到第n/2 + 1個(gè)節(jié)點(diǎn)）

5陨倡、從尾到頭打印敛滋，復(fù)雜度O(n)

原理：使用棧，后進(jìn)先出兴革。遞歸輸出pHead->next绎晃。

6、合并單鏈表杂曲，復(fù)雜度O(max(len1, len2))

類似歸并排序庶艾。

首先判斷兩鏈表都不為空；

定義合并后的鏈表的頭指針pHeadMerged = NULL擎勘，pHead1和pHead2比較后咱揍，賦值給pHeadMerged后，指向next棚饵；

定義pTemp = pHeadMerged煤裙，以p1 && p2都不為NULL為條件循環(huán)，p1p2判斷后賦值給temp->next（即賦值給pHeadMerged->next）蟹地，p1p2自身指向next积暖，temp指向temp->next，temp->next指向NULL怪与；

若p1或p2其中一個(gè)為NULL夺刑，則temp->next指向p1或p2，直接接入剩余鏈表

也可以使用遞歸的解法（比較耗費(fèi)空間但更簡(jiǎn)潔更容易理解）分别。

p1p2判斷后賦值給pHeadMerged（初始為NULL）遍愿；

pHeadMerged->next = 遞歸函數(shù)（p1->next/p2->next, p2/p1）

7、判斷是否有環(huán)耘斩，復(fù)雜度O(n)

最笨的方法是每次取一個(gè)節(jié)點(diǎn)循環(huán)遍歷比較沼填，復(fù)雜度O(n2)，顯然不夠優(yōu)雅

是否存在：應(yīng)使用一快一慢兩個(gè)指針pFast每次前進(jìn)兩步括授，pSlow每次前進(jìn)一步坞笙，相遇（pFast == pSlow）即有環(huán)。

環(huán)長(zhǎng)度：第一次相遇開始計(jì)數(shù)荚虚，第二次相遇結(jié)束時(shí)即環(huán)的長(zhǎng)度薛夜。ps：總長(zhǎng)度 = 環(huán)長(zhǎng)度+頭指針到環(huán)入口的距離。

環(huán)入口：定理版述，碰撞點(diǎn)到連接點(diǎn)的距離 = 頭指針到連接點(diǎn)的距離梯澜。分別從碰撞點(diǎn)和頭指針開始走，相遇即連接點(diǎn)渴析。

8晚伙、判斷兩單鏈表是否相交吮龄，復(fù)雜度O(len1+len2)

原理：相交的單鏈表尾節(jié)點(diǎn)相同，遍歷第一個(gè)鏈表咆疗，保存尾指針漓帚，遍歷第二個(gè)判斷是否尾指針相同，空間復(fù)雜度O(1)民傻。

求相交的第一個(gè)節(jié)點(diǎn)：先將長(zhǎng)的鏈表遍歷到len1- len2的節(jié)點(diǎn)胰默，此時(shí)，兩鏈表到第一節(jié)點(diǎn)距離相等漓踢，然后一起開始遍歷牵署，直到兩個(gè)節(jié)點(diǎn)地址相同即為第一個(gè)相交的節(jié)點(diǎn)。