基礎(chǔ)知識：

? ? ? ? 1.? 【鏈表的基本定義：】線性結(jié)構(gòu)利用指針連結(jié)在一起。這些線性結(jié)構(gòu)是指存儲東西的連結(jié)方式，其中要連結(jié)的是結(jié)點。

? ? ? ? ?2. ?【鏈表的結(jié)點】：分為數(shù)據(jù)域和指針域

?3.【鏈表的分類】：單鏈表、雙鏈表和循環(huán)鏈表

? ?其中單鏈表是“基本模型”，雙鏈表和循環(huán)鏈表是在他的基礎(chǔ)上改進的。

? ? ? ? ? ?3.1【雙鏈表】：其中的雙是指在原來一個指針域的基礎(chǔ)上，再添加一個指針域，這樣總的就有兩個指針域。

? ? ? ? ? 3.2【循環(huán)鏈表】：是指在單鏈表的基礎(chǔ)上，把最后指向NULL的指針，指向它的頭部

舉個例子：

? ? ? ??

【鏈表的基本定義的例子】?給要點餐的一群人排好序用計算機存儲起來。在計算機中我們可以采用 數(shù)組和鏈表。

【鏈表實際存儲數(shù)據(jù)的例子】

head 存放第一個結(jié)點的數(shù)據(jù)地址，第一個結(jié)點存放第二個結(jié)點的數(shù)據(jù)地址......

練習：

? 方法1：

還是比較簡單的，這里是學習了解法中的遞歸法。

【重點】：遞歸重點看return然后把return的結(jié)果和removeElenets對比來看。

方法2：虛擬頭結(jié)點：

? 引入：我們經(jīng)過第一個方法發(fā)現(xiàn)： 刪除結(jié)點的話，可能是頭結(jié)點，可能是除了頭結(jié)點的。所以奇思妙想的我們，想到用虛擬頭結(jié)點來解決這個問題，讓head不再是第一個了嘔。

第一步：我們來看看如何設(shè)置虛擬頭結(jié)點；

? ??

dummynode原本指向1結(jié)點，然后跨過去指向4。和原來的刪除結(jié)點差不多嘔。

第二步：代碼演示

【技術(shù)總結(jié)】:1.新申請了一個結(jié)點要用new?

? ? ? ? ? ? ? ? ? ? ? ? 2.這個結(jié)點也同樣使用了 cur來操作，來操作鏈表的走向。

? ? ? ? ? ? ? ? ? ? ? ?3.最后就是delete 多余的結(jié)點，最后head要更新。不然會出現(xiàn)鏈條斷不干凈。

這道題一共要實現(xiàn)的目標是 獲取第n個節(jié)點的值，頭部插入節(jié)點，尾部插入節(jié)點，第n個節(jié)點錢插入節(jié)點。刪第n個節(jié)點。

1.獲取第n個節(jié)點的值（利用虛擬頭結(jié)點）：

【技術(shù)總結(jié)】：

要引入一個temp中間變量來存儲，因為temp，因為cur改變指向，沒有指針再連結(jié)head了。所以要提前備份一個。

利用cur=temp來不斷遍歷鏈表