24. 兩兩交換鏈表中的節(jié)點
本題要求將相鄰的兩個節(jié)點交換拒课。
做題時候的難點：
1. 在遞歸和迭代之間猶豫不決。最后因為想到“交換后的節(jié)點對”的next還是“交換后的節(jié)點對”留拾。迭代法沒想出來如何實現(xiàn)，就用遞歸法了诬辈。
2. reverse函數(shù)只傳入一個節(jié)點拳昌。主要是考慮到：如果傳入兩個節(jié)點，比如current 和 current.next钳垮，那當current 為None的時候惑淳，生成輸入current.next就會報錯。
因為只傳入一個節(jié)點饺窿，那最終返回的就是current.next節(jié)點歧焦。但是在函數(shù)中current.next修改過，所以要用一個head暫存current.next節(jié)點肚医，否則就會報錯（寫的時候就犯錯了）
Carl講解：
1. 一定要記著绢馍，“交換節(jié)點對”，一定要在這對節(jié)點的前一個節(jié)點操作３μ住（這也就是為啥我之前想不出來迭代法如何實現(xiàn)）
2. 這道題要畫圖舰涌，因為鏈被重新連接，有些斷掉的點需要中間變量儲存你稚。
3. 卡哥強調終止條件是難點瓷耙。但個人覺得挺直觀，容易想到刁赖。
19.刪除鏈表的倒數(shù)第N個節(jié)點
本題要求刪除鏈表倒數(shù)第n個節(jié)點搁痛。使用快慢指針很直觀∮畛冢快指針先走n步落追，然后慢指針出發(fā)。當快指針到鏈表尾的時候涯肩，慢指針所指的就是要刪除的點轿钠。
做題時候的難點：
1. 如果快指針先走N步巢钓，剛好走到鏈尾，也就是fast為None疗垛。那要刪除的就是第一個節(jié)點症汹。此時應該返回head.next作為新的head
2. 卡哥的做法是加入一個虛擬頭結點，這樣不用特意處理頭結點贷腕。
160.?鏈表相交?
給出兩個單鏈表的頭結點背镇，返回他們的相交節(jié)點。思路：既然相交泽裳，那尾部應該是一樣的瞒斩。那就求出兩個鏈表的長度。求長度差N涮总，長鏈表先走N步后胸囱，短鏈表的指針也出發(fā)。兩指針相遇的點就是交點瀑梗。
做題時候的掙扎：
1. 找點的題目烹笔，能想到的就是兩指針相等（走到了同一個節(jié)點）。做題時在想有沒有其他的能判斷交點的方式抛丽，浪費時間....
最后還是妥協(xié)谤职。以兩指針相等作為判斷點。創(chuàng)造機會讓兩指針相等亿鲜。
142.環(huán)形鏈表II
判斷鏈表是否有環(huán)允蜈。如果有環(huán)返回環(huán)的入口。
快慢指針法：如果有環(huán)蒿柳，那么快慢指針必然相遇饶套。因為快指針先進入環(huán)，等慢指針進入環(huán)后其馏，快指針等于是每次一步的速度追趕慢指針。環(huán)周長N爆安，兩指針都在環(huán)內叛复，那快慢指針距離小于N。因此扔仓，慢指針走一圈的時間N褐奥，快指針一步一步必然能追上慢指針。
思路翘簇，創(chuàng)造一個兩指針相遇在環(huán)入口節(jié)點的機會撬码！
假設入口節(jié)點為x, 入環(huán)后再走y個點，快慢指針相遇版保，y再走z步又到入口節(jié)點x呜笑。則我們有2(x+y) = x + n(y+z) + y => x = (y+z) - y
這意味著夫否，如果有個新指針2, 在環(huán)內先走了y步，然后另個一個指針1從head出發(fā)叫胁，兩指針都走x步的時間凰慈，將會在環(huán)的入口相會。這就創(chuàng)造出了指針相等的條件驼鹅。
解題思路稍微有點難微谓。但代碼實現(xiàn)很簡單。
以下為卡哥的資料
?24.?兩兩交換鏈表中的節(jié)點?
用虛擬頭結點输钩，這樣會方便很多豺型。?
本題鏈表操作就比較復雜了，建議大家先看視頻买乃，視頻里我講解了注意事項姻氨，為什么需要temp保存臨時節(jié)點。
題目鏈接/文章講解/視頻講解：?https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
?19.刪除鏈表的倒數(shù)第N個節(jié)點??
雙指針的操作为牍，要注意哼绑，刪除第N個節(jié)點，那么我們當前遍歷的指針一定要指向?第N個節(jié)點的前一個節(jié)點碉咆，建議先看視頻抖韩。
?面試題?02.07.?鏈表相交??
本題沒有視頻講解，大家注意?數(shù)值相同疫铜，不代表指針相同茂浮。
?142.環(huán)形鏈表II??
算是鏈表比較有難度的題目，需要多花點時間理解?確定環(huán)和找環(huán)入口壳咕，建議先看視頻席揽。
題目鏈接/文章講解/視頻講解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
