單鏈表
- 單鏈表問題與思路
找出單鏈表的倒數(shù)第K個(gè)元素（僅允許遍歷一遍鏈表）
使用指針追趕的方法际跪。定義兩個(gè)指針fast和slow，fast先走K步闷愤，然后fast和slow同時(shí)繼續(xù)走整葡。當(dāng)fast到鏈表尾部時(shí)，slow指向倒數(shù)第K個(gè)讥脐。注意要考慮鏈表長(zhǎng)度應(yīng)該大于K找出單鏈表的中間元素（僅允許遍歷一遍鏈表）
使用指針追趕的方法遭居。fast每次走一步，slow每次走兩步旬渠。當(dāng)fast到鏈表尾部時(shí)俱萍，slow指向鏈表的中間元素。
判斷單鏈表是否有環(huán)告丢？
方法一：使用指針追趕的方法枪蘑。slow指針每次走一步，fast指針每次走兩步岖免。如存在環(huán)岳颇，則兩者相遇；如不存在環(huán)颅湘，fast遇到NULL退出话侧。
方法二：使用p、q兩個(gè)指針栅炒，p總是向前走掂摔，但q每次都從頭開始走。如何知道環(huán)的長(zhǎng)度赢赊？
記錄下碰撞點(diǎn)（或者找在環(huán)中任意一結(jié)點(diǎn)都可以）乙漓，讓slow從碰撞點(diǎn)開始，繞著環(huán)走一圈释移，再次到碰撞點(diǎn)的位置時(shí)叭披，所走過的結(jié)點(diǎn)數(shù)就是環(huán)的長(zhǎng)度s。如何找到環(huán)的入口玩讳？
分別從碰撞點(diǎn)、頭指針開始走同诫，相遇的那個(gè)點(diǎn)就是連接點(diǎn)。-
判斷兩個(gè)鏈表（無環(huán)）是否相交？
方法一：采用暴力的方法想际，遍歷兩個(gè)鏈表，在遍歷的過程中進(jìn)行比較，看節(jié)點(diǎn)是否相同妆档。方法二：兩鏈表一旦相交，相交節(jié)點(diǎn)一定有相同的內(nèi)存地址，因此利用內(nèi)存地址建立哈希表甜奄，如此通過判斷兩個(gè)鏈表中是否存在內(nèi)存地址相同的節(jié)點(diǎn)判斷兩個(gè)鏈表是否相交烟阐。具體做法是：遍歷第一個(gè)鏈表，并利用地址建立哈希表卵凑，遍歷第二個(gè)鏈表，看看地址哈希值是否和第一個(gè)表中的節(jié)點(diǎn)地址值有相同即可判斷兩個(gè)鏈表是否相交黑忱。時(shí)間復(fù)雜度O(（length（A）+ length（B))
方法三：問題轉(zhuǎn)化法宴抚。先遍歷第一個(gè)鏈表到其尾部，然后將尾部的原本指向NULL的next指針指向第二個(gè)鏈表甫煞。這樣兩個(gè)鏈表就合成了一個(gè)鏈表菇曲，問題轉(zhuǎn)變?yōu)榕袛嘈碌逆湵硎欠裼协h(huán)？
方法四：一旦兩個(gè)鏈表相交抚吠，那么兩個(gè)鏈表從相交節(jié)點(diǎn)開始到尾節(jié)點(diǎn)一定都是相同的節(jié)點(diǎn)常潮。所以，如果他們相交的話楷力，那么他們最后的一個(gè)節(jié)點(diǎn)一定是相同的喊式，因此分別遍歷到兩個(gè)鏈表的尾部，然后判斷他們是否相同萧朝。
如何知道兩個(gè)單鏈表（可能有環(huán)）是否相交
思路：根據(jù)兩個(gè)鏈表是否有環(huán)來分別處理岔留，若相交這個(gè)環(huán)屬于兩個(gè)鏈表共有
（1）如果兩個(gè)鏈表都沒有環(huán)。
（2）一個(gè)有環(huán)剪勿，一個(gè)沒環(huán)贸诚。肯定不相交
（3）兩個(gè)都有環(huán)厕吉。
①求出A的環(huán)入口酱固，判斷其是否在B鏈表上，如果在头朱，則相交运悲。
② 在A鏈表上，使用指針追趕的方法项钮，找到兩個(gè)指針碰撞點(diǎn)班眯，之后判斷碰撞點(diǎn)是否在B鏈表上希停。如果在，則相交署隘。尋找兩個(gè)相交鏈表的第一個(gè)公共節(jié)點(diǎn)
方法一：最簡(jiǎn)單的方法就是先順序訪問其中一個(gè)鏈表宠能，在每訪問一個(gè)節(jié)點(diǎn)時(shí)，都對(duì)另外一個(gè)鏈表進(jìn)行遍歷磁餐，直到找到一個(gè)相等的節(jié)點(diǎn)位置违崇，如果鏈表長(zhǎng)度分別是m,n 則時(shí)間復(fù)雜度為O(mn)。
方法二：（兩種情況）
① 相交的點(diǎn)诊霹，在環(huán)外羞延。如果兩個(gè)鏈表有公共節(jié)點(diǎn)，那么該公共節(jié)點(diǎn)之后的所有節(jié)點(diǎn)都是兩個(gè)鏈表所共有的脾还，所以長(zhǎng)度一定也是相等的伴箩，如果兩個(gè)鏈表的總長(zhǎng)度是相等的，那么我們對(duì)兩個(gè)鏈表進(jìn)行遍歷鄙漏，則一定同時(shí)到達(dá)第一個(gè)公共節(jié)點(diǎn)嗤谚。但是鏈表的長(zhǎng)度實(shí)際上不一定相同，所以計(jì)算出兩個(gè)鏈表的長(zhǎng)度之差n泥张，然后讓長(zhǎng)的那個(gè)鏈表先移動(dòng)n步呵恢，短的鏈表再開始向后遍歷，這樣他們一定同時(shí)到達(dá)第一個(gè)公共節(jié)點(diǎn)媚创，我們只需要在向后移動(dòng)的時(shí)候比較兩個(gè)鏈表的節(jié)點(diǎn)是否相等就可以獲得第一個(gè)公共節(jié)點(diǎn)。時(shí)間復(fù)雜度是O(m+n)彤恶。
② 相交的點(diǎn)在環(huán)內(nèi)钞钙。當(dāng)交點(diǎn)在環(huán)中時(shí)，此時(shí)的交點(diǎn)可以是A鏈表中的環(huán)入口點(diǎn)声离，也可以是B鏈表中環(huán)入口點(diǎn)芒炼。這是因?yàn)槿绻袯看出一個(gè)完整的鏈表，而A指向了B鏈表术徊，則此時(shí)交點(diǎn)是A的環(huán)入口點(diǎn)本刽。反之交點(diǎn)是鏈表B的環(huán)入口點(diǎn)。
思路：根據(jù)上述分析赠涮，可以直接求出A的環(huán)入口點(diǎn)或者B的環(huán)入口點(diǎn)就可以了子寓。
- 單鏈表代碼實(shí)現(xiàn)
鏈表結(jié)點(diǎn)聲明如下：
struct ListNode{
int m_nKey;
ListNode * m_pNext;
};
- 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)
這是最最基本的了，應(yīng)該能夠迅速寫出正確的代碼笋除，注意檢查鏈表是否為空斜友。時(shí)間復(fù)雜度為O（n）。參考代碼如下：
1. // 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)
2. unsigned int GetListLength(ListNode * pHead)
3. {
4. if(pHead == NULL)
5. return 0;
6.
7. unsigned int nLength = 0;
8. ListNode * pCurrent = pHead;
9. while(pCurrent != NULL)
10. {
11. nLength++;
12. pCurrent = pCurrent->m_pNext;
13. }
14. return nLength;
15. }
- 找到單鏈表的中間節(jié)點(diǎn)：
SListNode* FindMidNode(SListNode* pHead)//pHead是鏈表的頭節(jié)點(diǎn)
{
SListNode* fast = pHead;
SListNode* slow = pHead;
while (fast->next)
{
slow = slow->next;
fast = fast->next;
if (fast->next)
{
fast = fast->next;
}
else
{
break;
}
}
return slow;
}
- 判斷一個(gè)鏈表是否帶環(huán)垃它，若帶返回環(huán)的入口點(diǎn)（較難）
上面已經(jīng)說過鲜屏，通過快慢指針可以找到單鏈表中的任何節(jié)點(diǎn)烹看，這也是通過驗(yàn)證的。那么原理上也可以判斷鏈表是否帶環(huán)：
如果帶環(huán)洛史，快慢指針一定會(huì)在某個(gè)節(jié)點(diǎn)處相遇惯殊。（fast一直在環(huán)里轉(zhuǎn)，總有一個(gè)時(shí)刻也殖，slow追上fast土思，相遇）
1. SListNode* WhetherRing(SListNode* pHead)//判斷是否帶環(huán)，若帶毕源，返回相遇節(jié)點(diǎn)
2. {
3. if (pHead == NULL||pHead->next == NULL)
4. return NULL;
5. SListNode* fast = pHead;
6. SListNode* slow = pHead;
7. while (fast)
8. {
9. slow = slow->next;
10. fast = fast->next;
11. if (fast)
12. {
13. fast = fast->next;
14. }
15. else
16. {
17. return NULL;//沒有環(huán)
18. }
19. if (fast == slow)
20. {
21. return slow;//有環(huán)
22. }
23. }
24. return NULL;
25. }
如果鏈表帶環(huán)的話浪漠，我們就可以求出相遇的節(jié)點(diǎn)。然后從相遇節(jié)點(diǎn)處斷開帶環(huán)鏈表霎褐，一個(gè)指針從鏈表投節(jié)點(diǎn)處開始往后遍歷址愿，一個(gè)指針從斷開處往后遍歷，相遇節(jié)點(diǎn)處就是環(huán)的入口點(diǎn)
1. SListNode* GetEnterNode(SListNode* pHead)//找到鏈表環(huán)入口節(jié)點(diǎn)在哪（重點(diǎn)）
2. {
3. SListNode* start = pHead;
4. SListNode* tmp = WhetherRing(pHead);
5. while (start != tmp)
6. {
7. start = start->next;
8. tmp = tmp->next;
9. }
10. return start;
11. }
- 將單鏈表反轉(zhuǎn)
從頭到尾遍歷原鏈表冻璃，每遍歷一個(gè)結(jié)點(diǎn)响谓，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況省艳。時(shí)間復(fù)雜度為O（n）娘纷。參考代碼如下：
1. // 反轉(zhuǎn)單鏈表
2. ListNode * ReverseList(ListNode * pHead)
3. {
4. // 如果鏈表為空或只有一個(gè)結(jié)點(diǎn)，無需反轉(zhuǎn)跋炕，直接返回原鏈表頭指針
5. if(pHead == NULL || pHead->m_pNext == NULL)
6. return pHead;
7.
8. ListNode * pReversedHead = NULL; // 反轉(zhuǎn)后的新鏈表頭指針赖晶，初始為NULL
9. ListNode * pCurrent = pHead;
10. while(pCurrent != NULL)
11. {
12. ListNode * pTemp = pCurrent;
13. pCurrent = pCurrent->m_pNext;
14. pTemp->m_pNext = pReversedHead; // 將當(dāng)前結(jié)點(diǎn)摘下，插入新鏈表的最前端
15. pReversedHead = pTemp;
16. }
17. return pReversedHead;
18. }
- 查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn)（k > 0）
最普遍的方法是辐烂，先統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)遏插，然后再找到第（n-k）個(gè)結(jié)點(diǎn)。注意鏈表為空纠修，k為0胳嘲，k為1，k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)時(shí)的情況扣草。時(shí)間復(fù)雜度為O（n）了牛。代碼略。
這里主要講一下另一個(gè)思路辰妙，這種思路在其他題目中也會(huì)有應(yīng)用鹰祸。
主要思路就是使用兩個(gè)指針，先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn)上岗，這樣前后兩個(gè)指針的距離差是k-1福荸，之后前后兩個(gè)指針一起向前走，前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)肴掷，后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)敬锐。
參考代碼如下：
1. // 查找單鏈表中倒數(shù)第K個(gè)結(jié)點(diǎn)
2. ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函數(shù)名前面的R代表反向
3. {
4. if(k == 0 || pHead == NULL) // 這里k的計(jì)數(shù)是從1開始的背传，若k為0或鏈表為空返回NULL
5. return NULL;
6.
7. ListNode * pAhead = pHead;
8. ListNode * pBehind = pHead;
9. while(k > 1 && pAhead != NULL) // 前面的指針先走到正向第k個(gè)結(jié)點(diǎn)
10. {
11. pAhead = pAhead->m_pNext;
12. k--;
13. }
14. if(k > 1 || pAhead == NULL) // 結(jié)點(diǎn)個(gè)數(shù)小于k，返回NULL
15. return NULL;
16. while(pAhead->m_pNext != NULL) // 前后兩個(gè)指針一起向前走台夺，直到前面的指針指向最后一個(gè)結(jié)點(diǎn)
17. {
18. pBehind = pBehind->m_pNext;
19. pAhead = pAhead->m_pNext;
20. }
21. return pBehind; // 后面的指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)
22. }
- 從尾到頭打印單鏈表
對(duì)于這種顛倒順序的問題径玖，我們應(yīng)該就會(huì)想到棧，后進(jìn)先出颤介。所以梳星，這一題要么自己使用棧，要么讓系統(tǒng)使用棧滚朵，也就是遞歸冤灾。注意鏈表為空的情況。時(shí)間復(fù)雜度為O（n）辕近。參考代碼如下：
自己使用棧：
1. // 從尾到頭打印鏈表韵吨，使用棧
2. void RPrintList(ListNode * pHead)
3. {
4. std::stack<ListNode *> s;
5. ListNode * pNode = pHead;
6. while(pNode != NULL)
7. {
8. s.push(pNode);
9. pNode = pNode->m_pNext;
10. }
11. while(!s.empty())
12. {
13. pNode = s.top();
14. printf("%d\t", pNode->m_nKey);
15. s.pop();
16. }
17. }
使用遞歸函數(shù)：
1. // 從尾到頭打印鏈表，使用遞歸
2. void RPrintList(ListNode * pHead)
3. {
4. if(pHead == NULL)
5. {
6. return;
7. }
8. else
9. {
10. RPrintList(pHead->m_pNext);
11. printf("%d\t", pHead->m_nKey);
12. }
13. }
- 已知兩個(gè)單鏈表pHead1 和pHead2 各自有序移宅，把它們合并成一個(gè)鏈表依然有序
這個(gè)類似歸并排序归粉。尤其注意兩個(gè)鏈表都為空，和其中一個(gè)為空時(shí)的情況漏峰。只需要O（1）的空間糠悼。時(shí)間復(fù)雜度為O（max(len1, len2)）。參考代碼如下：
1. ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)
2. {
3. if(pHead1 == NULL)
4. return pHead2;
5. if(pHead2 == NULL)
6. return pHead1;
7. ListNode * pHeadMerged = NULL;
8. if(pHead1->m_nKey < pHead2->m_nKey)
9. {
10. pHeadMerged = pHead1;
11. pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);
12. }
13. else
14. {
15. pHeadMerged = pHead2;
16. pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);
17. }
18. return pHeadMerged;
19. }
- 判斷一個(gè)單鏈表中是否有環(huán)
這里也是用到兩個(gè)指針浅乔。如果一個(gè)鏈表中有環(huán)倔喂，也就是說用一個(gè)指針去遍歷，是永遠(yuǎn)走不到頭的靖苇。因此滴劲，我們可以用兩個(gè)指針去遍歷，一個(gè)指針一次走兩步顾复，一個(gè)指針一次走一步，如果有環(huán)鲁捏，兩個(gè)指針肯定會(huì)在環(huán)中相遇芯砸。時(shí)間復(fù)雜度為O（n）。參考代碼如下：
1. bool HasCircle(ListNode * pHead)
2. {
3. ListNode * pFast = pHead; // 快指針每次前進(jìn)兩步
4. ListNode * pSlow = pHead; // 慢指針每次前進(jìn)一步
5. while(pFast != NULL && pFast->m_pNext != NULL)
6. {
7. pFast = pFast->m_pNext->m_pNext;
8. pSlow = pSlow->m_pNext;
9. if(pSlow == pFast) // 相遇给梅，存在環(huán)
10. return true;
11. }
12. return false;
13. }
- 給出一單鏈表頭指針pHead和一節(jié)點(diǎn)指針pToBeDeleted假丧，O(1)時(shí)間復(fù)雜度刪除節(jié)點(diǎn)pToBeDeleted
對(duì)于刪除節(jié)點(diǎn)，我們普通的思路就是讓該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)动羽，這種情況需要遍歷找到該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)包帚，時(shí)間復(fù)雜度為O(n)。對(duì)于鏈表运吓，鏈表中的每個(gè)節(jié)點(diǎn)結(jié)構(gòu)都是一樣的渴邦，所以我們可以把該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到該節(jié)點(diǎn)疯趟，然后刪除下一個(gè)節(jié)點(diǎn)即可。要注意最后一個(gè)節(jié)點(diǎn)的情況谋梭，這個(gè)時(shí)候只能用常見的方法來操作信峻，先找到前一個(gè)節(jié)點(diǎn)，但總體的平均時(shí)間復(fù)雜度還是O(1)瓮床。參考代碼如下：
1. void Delete(ListNode * pHead, ListNode * pToBeDeleted)
2. {
3. if(pToBeDeleted == NULL)
4. return;
5. if(pToBeDeleted->m_pNext != NULL)
6. {
7. pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; // 將下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到本節(jié)點(diǎn)盹舞，然后刪除下一個(gè)節(jié)點(diǎn)
8. ListNode * temp = pToBeDeleted->m_pNext;
9. pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
10. delete temp;
11. }
12. else // 要?jiǎng)h除的是最后一個(gè)節(jié)點(diǎn)
13. {
14. if(pHead == pToBeDeleted) // 鏈表中只有一個(gè)節(jié)點(diǎn)的情況
15. {
16. pHead = NULL;
17. delete pToBeDeleted;
18. }
19. else
20. {
21. ListNode * pNode = pHead;
22. while(pNode->m_pNext != pToBeDeleted) // 找到倒數(shù)第二個(gè)節(jié)點(diǎn)
23. pNode = pNode->m_pNext;
24. pNode->m_pNext = NULL;
25. delete pToBeDeleted;
26. }
27. }
28. }
