今天的題目都是單項(xiàng)鏈表，單向鏈表的特點(diǎn)是只能單向遍歷做裙。主要的優(yōu)化角度在于減少內(nèi)存使用岗憋。
24.?兩兩交換鏈表中的節(jié)點(diǎn)?
用虛擬頭結(jié)點(diǎn)，這樣會(huì)方便很多锚贱。?
本題鏈表操作就比較復(fù)雜了仔戈，建議大家先看視頻，視頻里我講解了注意事項(xiàng)拧廊，為什么需要temp保存臨時(shí)節(jié)點(diǎn)杂穷。題目鏈接/文章講解/視頻講解。
這個(gè)題寫(xiě)了兩種解法卦绣，dummy_head直接寫(xiě)，理清楚順序飞蚓；第二個(gè)方法是遞歸滤港，while內(nèi)部的動(dòng)作其實(shí)是重復(fù)的即遞歸思想，這樣可以省卻了while以及init的處理。
這個(gè)題再次體現(xiàn)了C++語(yǔ)法的精準(zhǔn)性溅漾，每一個(gè)指針指向的元素是什么都非常的清晰山叮，非常有利于把抽象問(wèn)題具體化，很適合加深理解數(shù)據(jù)結(jié)構(gòu)添履。
Python方法一：dummy_head暴力遍歷：
試了兩種寫(xiě)交換元素的方法屁倔，如果同時(shí)寫(xiě)，那么同時(shí)交換暮胧，不用寫(xiě)tmp元素锐借；如果逐行寫(xiě)，需要想清楚先后順序往衷，并且創(chuàng)建中間tmp元素钞翔。第二種較為簡(jiǎn)潔。
Python方法二：遞歸
也可以用遞歸來(lái)寫(xiě)席舍，相對(duì)比較簡(jiǎn)潔布轿。不用處理init和while的細(xì)節(jié)，且需要交換的元素較少来颤。
C++方法一：dummy_head暴力遍歷：
記得清除緩存變量汰扭。
c++ 不像 python，go 那種能這樣交換兩個(gè)變量的值福铅。逗號(hào)運(yùn)算符它會(huì)忽略掉左邊的表達(dá)式萝毛。所以這里沒(méi)有Python的簡(jiǎn)潔版寫(xiě)法。只能利用中間變量逐步替換本讥。
C++方法二：遞歸
19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)??
雙指針的操作珊泳，要注意，刪除第N個(gè)節(jié)點(diǎn)拷沸，那么我們當(dāng)前遍歷的指針一定要指向?第N個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)色查，建議先看視頻。題目鏈接/文章講解/視頻講解撞芍。
第一直覺(jué)是秧了，遍歷兩遍，第一遍確定ListNode長(zhǎng)度序无，第二遍刪除第size-n個(gè)元素验毡；遍歷兩遍提示我們可以用快慢指針來(lái)做，fast先走n步帝嗡，再同時(shí)走slow fast直至最后一個(gè)node晶通。細(xì)節(jié)上需要注意的是，考慮到n=1的情況哟玷，即刪除最后一個(gè)元素狮辽，需要在倒數(shù)第二個(gè)元素時(shí)就決定，用dummy_head實(shí)現(xiàn)。
Python版本：
C++版本：
C++ 語(yǔ)法：
C++刪除記得釋放內(nèi)存喉脖。
n--的用法是新學(xué)的椰苟。?C++：i++、++i树叽、--i舆蝴、i--、+=题诵、-=洁仗、*=、/=你真的了解嗎仇轻？
總是寫(xiě)錯(cuò)調(diào)用類(lèi)屬性的方式京痢，head->next 而非head.next。
160.?鏈表相交??
本題沒(méi)有視頻講解篷店，大家注意?數(shù)值相同祭椰，不代表指針相同。題目鏈接/文章講解疲陕。
這個(gè)題和19題類(lèi)似用到了快慢指針方淤，思考邏輯是：如果倒過(guò)來(lái)遍歷，那么最長(zhǎng)的相同的node就是答案蹄殃。而單鏈表只能單個(gè)方向遍歷携茂，于是需要先統(tǒng)計(jì)出兩個(gè)鏈表的長(zhǎng)度，求出長(zhǎng)度差诅岩，之后的步驟就和19題類(lèi)似了讳苦，快慢指針。
Leetcode在LinkList輸出無(wú)效值的時(shí)候吩谦，輸出None鸳谜，不能空白或者輸出int(0)。
Python版本：
C++版本：
142.環(huán)形鏈表II??
算是鏈表比較有難度的題目式廷，需要多花點(diǎn)時(shí)間理解?確定環(huán)和找環(huán)入口咐扭，建議先看視頻。題目鏈接/文章講解/視頻講解滑废。
目前比較有意思的一個(gè)題蝗肪，方法一是遍歷，記錄出現(xiàn)過(guò)的node蠕趁，第二次出現(xiàn)的node即為入口薛闪，時(shí)間O(n)， 但是內(nèi)存[1+2+3+...+n ~ n^2]俺陋。那么就開(kāi)始考慮是否可以?xún)?yōu)化內(nèi)存到O(n)逛绵，這個(gè)思路是經(jīng)典的龜兔賽跑問(wèn)題怀各，用快慢指針的話(huà)一定會(huì)相遇，且圖中x=z术浪，在快指針只套了慢指針一圈的情況下，如果快指針比慢指針快了n圈（n>=2）的推導(dǎo)就比較妙了寿酌，x = （y+z）*k + z胰苏， 發(fā)現(xiàn)和n=1的情況是一樣的，所以當(dāng)快慢指針在met處相遇后醇疼，把慢指針?lè)呕豩ead硕并，那么下一次快慢指針相遇一定在x處。核心仍然是x=z秧荆。
Python方法一：暴力遍歷
Python方法二：快慢指針
C++方法一：暴力遍歷
C++關(guān)于集合的數(shù)據(jù)結(jié)構(gòu)有set, unordered_set, map, unordered_map; unordered_set更接近Python中的set概念倔毙，但是這個(gè)題不能用unordered_set,因?yàn)?/a>集合內(nèi)部元素是LinkList, unordered_set底層是hash_table, LinkList沒(méi)有對(duì)應(yīng)的hash函數(shù)，故不支持乙濒。所以適合map結(jié)構(gòu)陕赃，map結(jié)構(gòu)內(nèi)部可以是LinkNode作為key。
C++方法二：快慢指針
