基本概念

鏈表的含義：

鏈表是一種用于存儲(chǔ)數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)献烦，具有以下屬性

• 相鄰元素之間通過(guò)指針相連
• 最后一個(gè)元素的后繼指針為NULL
• 在程序執(zhí)行過(guò)程中唠粥，鏈表的長(zhǎng)度可以增加或減小
• 鏈表的空間能夠按需分配（直到系統(tǒng)內(nèi)存耗盡）

• 沒(méi)有內(nèi)存空間的浪費(fèi)（但鏈表中的指針需要一些額外的內(nèi)存開(kāi)銷）

  
  
  image.png

鏈表的操作：

• 插入：插入一個(gè)元素到鏈表中
• 刪除：移除并返回鏈表中指定位置的元素
• 刪除鏈表：清空鏈表中的全部元素
• 計(jì)數(shù)：返回鏈表中元素的個(gè)數(shù)
• 查找：尋找從鏈表表頭開(kāi)始的第n個(gè)節(jié)點(diǎn)（node）

鏈表與數(shù)組的比較：

鏈表和數(shù)組都可用于存儲(chǔ)數(shù)據(jù)集合链患，但兩者的用法還是有些許不同，下面對(duì)兩種的異同進(jìn)行比對(duì)

image.png

數(shù)組的優(yōu)點(diǎn)：

• 實(shí)現(xiàn)簡(jiǎn)單，使用方便
• 訪問(wèn)元素快（常數(shù)時(shí)間）

數(shù)組的缺點(diǎn)：

• 大小固定：數(shù)組的大小是靜態(tài)的（需要在使用前聲明其大小）
• 分配一個(gè)連續(xù)的空間塊：數(shù)組初始分配空間時(shí)族铆，有時(shí)內(nèi)存不足以給出一個(gè)連續(xù)的空間以存放數(shù)組（當(dāng)數(shù)組過(guò)大或者內(nèi)存碎片過(guò)多時(shí)）
• 基于位置的插入操作實(shí)現(xiàn)復(fù)雜：如果要在數(shù)組的指定位置插入元素，可能需要移動(dòng)存儲(chǔ)在數(shù)組中的其他元素哭尝。指定的位置越靠前哥攘，移動(dòng)操作的開(kāi)銷也就越大。

數(shù)組的改進(jìn)：

image.png

鏈表的主要優(yōu)點(diǎn)：

• 鏈表的擴(kuò)展和收縮都是常數(shù)時(shí)間材鹦。當(dāng)創(chuàng)建數(shù)組時(shí)逝淹，必須分配能存儲(chǔ)一定數(shù)量元素的內(nèi)存。如果向數(shù)組中添加更多元素桶唐，必須創(chuàng)建一個(gè)新的數(shù)組栅葡，然后把原數(shù)組中的元素復(fù)制到新數(shù)組中，這將產(chǎn)生很大的開(kāi)銷莽红。
• 當(dāng)然可以為數(shù)組預(yù)先分配一個(gè)很大的空間來(lái)預(yù)防上述情況的發(fā)生妥畏，但很可能因?yàn)榉峙涑^(guò)用戶需要的空間而造成內(nèi)存浪費(fèi)邦邦。動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)也是基于上文所述的原理安吁。而對(duì)于鏈表，初始時(shí)僅需要分配一個(gè)元素的存儲(chǔ)空間燃辖，而且添加新的元素也很容易鬼店，不需要做任何內(nèi)存復(fù)制和重新分配的操作。

鏈表的缺點(diǎn)：

• 鏈表最主要的缺點(diǎn)就是訪問(wèn)單個(gè)元素的時(shí)間開(kāi)銷問(wèn)題黔龟。數(shù)組是隨機(jī)存取的妇智，即存取數(shù)組中任一元素的時(shí)間開(kāi)銷為氏身。而鏈表在最差情況下訪問(wèn)一個(gè)元素的時(shí)間開(kāi)銷是到踏。同時(shí)數(shù)組在存取時(shí)間的另一個(gè)優(yōu)點(diǎn)是內(nèi)存的空間局部性耙旦。因?yàn)閿?shù)組定義為連續(xù)的內(nèi)存塊绢陌，所以任何數(shù)組元素與其鄰居是物理相鄰的闻鉴。這一點(diǎn)歸功于現(xiàn)代的CPU緩存模式授艰。
• 盡管鏈表在動(dòng)態(tài)分配存儲(chǔ)空間上有很大優(yōu)勢(shì)，但在存儲(chǔ)和檢索數(shù)據(jù)的開(kāi)銷卻有很大問(wèn)題垦缅。尤其是對(duì)鏈表的操作很麻煩。比如要?jiǎng)h除鏈表最后一個(gè)元素，倒數(shù)第二個(gè)結(jié)點(diǎn)必須更改后繼結(jié)點(diǎn)為NULL缅阳，而這需要從頭遍歷鏈表昌渤，直到找到倒數(shù)第二個(gè)結(jié)點(diǎn)潜支。相當(dāng)于為了刪除一個(gè)元素，需要遍歷兩遍鏈表柿汛。（后續(xù)程序中為避免這一點(diǎn)冗酿，用一個(gè)臨時(shí)結(jié)點(diǎn)存儲(chǔ)當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)）
• 鏈表中的額外指針引用需要消耗內(nèi)存

image.png

單向鏈表

最常用的鏈表就是單向鏈表，它包含多個(gè)結(jié)點(diǎn)络断，每個(gè)節(jié)點(diǎn)有一個(gè)指向后繼元素的next指針裁替，最后一個(gè)結(jié)點(diǎn)的next指針為NULL，表示鏈表的結(jié)束

image.png

image.png

下面我們看一下單向鏈表的三種基本操作：遍歷鏈表妓羊，在鏈表中插入一個(gè)元素胯究，在鏈表中刪除一個(gè)元素

單向鏈表的遍歷

image.png

單向鏈表的插入
單向鏈表的插入可分為以下三種情況：

• 在鏈表的表頭前插入一個(gè)新的結(jié)點(diǎn)（相當(dāng)于在原表頭前插入一個(gè)新表頭）
• 在鏈表的表尾后插入一個(gè)新的結(jié)點(diǎn)（相當(dāng)于在原尾結(jié)點(diǎn)后添加一個(gè)新尾結(jié)點(diǎn)）
• 在鏈表的中間插入一個(gè)新的結(jié)點(diǎn)（第一二種情況外的任意位置）
  這里我們說(shuō)在位置p插入一個(gè)結(jié)點(diǎn)，是說(shuō)新的結(jié)點(diǎn)位置是p

image.png

image.png

image.png

image.png

image.png

單向鏈表的刪除
與插入類似躁绸，刪除也分為三種情況：

• 刪除鏈表的表頭結(jié)點(diǎn)
• 刪除鏈表的表尾結(jié)點(diǎn)
• 刪除鏈表中間的節(jié)點(diǎn)

image.png

image.png

image.png

image.png

image.png

image.png

這里值得注意的是其中的clear方法僅僅是將head置為空，如有size則置為0臣嚣，在LinkedList源碼中净刮，其實(shí)現(xiàn)如下

 /**
     * Removes all of the elements from this list.
     * The list will be empty after this call returns.
     */
    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

關(guān)鍵在于源碼中的兩行注釋

• 當(dāng)遺棄的結(jié)點(diǎn)在不止一代中（新生代和老年代）存在，可以幫助分代收集器GC
• 即便有一個(gè)關(guān)于linkedlist的可達(dá)的迭代器存在硅则，也可以保證鏈表中的結(jié)點(diǎn)的內(nèi)存被回收（不然會(huì)造成雖然頭尾結(jié)點(diǎn)都是Null淹父，但如果一個(gè)迭代器作為GC root，其中l(wèi)astReturned指向一個(gè)結(jié)點(diǎn)怎虫，這個(gè)結(jié)點(diǎn)還有前驅(qū)和后繼結(jié)點(diǎn)暑认，最終導(dǎo)致所有結(jié)點(diǎn)都得不到釋放困介，即便此時(shí)頭尾結(jié)點(diǎn)已經(jīng)無(wú)法遍歷至其他結(jié)點(diǎn)了）

// LinkedList中迭代器部分源碼
private class ListItr implements ListIterator<E> {  
    private Entry<E> lastReturned = header;  
    private Entry<E> next;  
    private int nextIndex;  
    private int expectedModCount = modCount;  
  
    ListItr(int index) {  
        if (index < 0 || index > size)  
        throw new IndexOutOfBoundsException("Index: "+index+  
                            ", Size: "+size);  
        if (index < (size >> 1)) {  
        next = header.next;  
        for (nextIndex=0; nextIndex<index; nextIndex++)  
            next = next.next;  
        } else {  
        next = header;  
        for (nextIndex=size; nextIndex>index; nextIndex--)  
            next = next.previous;  
        }  
    }  
  
    public boolean hasNext() {  
        return nextIndex != size;  
    }  
  
    public E next() {  
        checkForComodification();  
        if (nextIndex == size)  
        throw new NoSuchElementException();  
  
        lastReturned = next;  
        next = next.next;  
        nextIndex++;  
        return lastReturned.element;  
    }  
......  
}  

綜上所述，因此源碼實(shí)現(xiàn)才會(huì)在將基礎(chǔ)的頭尾結(jié)點(diǎn)置空蘸际，size置0之前座哩，將每個(gè)結(jié)點(diǎn)的值，前驅(qū)和后繼結(jié)點(diǎn)都置為空粮彤，當(dāng)然我們這里實(shí)現(xiàn)的最基礎(chǔ)的鏈表功能是不需要考慮這么多的根穷。

雙向鏈表

雙向鏈表的特點(diǎn)是：對(duì)于鏈表中一個(gè)給定的結(jié)點(diǎn)，可以從兩個(gè)方向來(lái)操作导坟。在單向鏈表中屿良，只有獲得結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，才能刪除該結(jié)點(diǎn)惫周。然而在雙向鏈表中尘惧，即使沒(méi)有獲得一個(gè)給定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，也可以刪除該結(jié)點(diǎn)（這是因?yàn)殡p向鏈表的每個(gè)結(jié)點(diǎn)都有next指針同時(shí)還有previous指針指向前驅(qū)結(jié)點(diǎn)）
然而與單向鏈表相比：

• 每個(gè)結(jié)點(diǎn)需要添加一個(gè)額外的指針递递，因此需要更多空間開(kāi)銷
• 結(jié)點(diǎn)的插入和刪除更加費(fèi)時(shí)（需要更多的指針操作）

下面是一個(gè)雙向鏈表的類型聲明

image.png

image.png

image.png

image.png

image.png

image.png

image.png

雙向鏈表的刪除

image.png

image.png

image.png

image.png

循環(huán)鏈表

單向鏈表和雙向鏈表中都用NULL表示鏈表的結(jié)束，然而循環(huán)鏈表沒(méi)有結(jié)束標(biāo)志（沒(méi)有next為NULL的情況）漾狼。因此遍歷循環(huán)鏈表需要格外小心重慢，因?yàn)槊恳粋€(gè)結(jié)點(diǎn)都有一個(gè)后繼結(jié)點(diǎn)，會(huì)導(dǎo)致遍歷無(wú)限循環(huán)下去逊躁。

循環(huán)鏈表在某些情況下是很有用的似踱，例如多個(gè)進(jìn)程都想使用CPU資源，并且它們使用該資源的時(shí)間也相同稽煤，為了防止某個(gè)進(jìn)程總是排在其他進(jìn)程前面核芽，通過(guò)循環(huán)鏈表實(shí)現(xiàn)的輪詢算法可以保證公平。

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

題外話：鏈表中的哨兵

注意到我們對(duì)于鏈表的操作牽扯到插入和刪除時(shí)酵熙，無(wú)論是單鏈表轧简，雙向鏈表還是循環(huán)鏈表，都要根據(jù)頭部操作匾二，尾部操作和中間操作的不同分為多種情況哮独，下面我們引入哨兵這個(gè)概念：

哨兵，顧名思義察藐，是用來(lái)解決國(guó)家之間邊界問(wèn)題的皮璧，不直接參與生產(chǎn)活動(dòng)。
同樣分飞，計(jì)算機(jī)科學(xué)中提到的哨兵悴务，也用來(lái)解決邊界問(wèn)題。
在許多算法中譬猫，存在“鄰居依賴問(wèn)題”讯檐，在處理當(dāng)前元素時(shí)羡疗，要涉及到它旁邊那個(gè)元素。那如果當(dāng)前元素是邊界元素時(shí)别洪，它沒(méi)有旁邊那個(gè)元素叨恨，此時(shí)不作處理，程序就可能出錯(cuò)蕉拢；但對(duì)它特別對(duì)待特碳，就會(huì)增加代碼復(fù)雜性，還會(huì)降低程序效率晕换。應(yīng)用哨兵午乓，也就是申請(qǐng)若干個(gè)多余的元素作為邊界元素的鄰居，可以完美得解決這個(gè)問(wèn)題闸准。

比如在n*m的矩形區(qū)域中益愈，例如掃雷，一個(gè)點(diǎn)擊方塊時(shí)夷家，要掃描周圍8個(gè)方塊的雷數(shù)蒸其，而邊界方塊的周圍不足8個(gè)方塊，一種解決方法就是在有效矩形區(qū)域的周圍库快，添加一圈的方塊摸袁，

但這個(gè)方法申請(qǐng)的哨兵數(shù)量有點(diǎn)多，數(shù)量是2n+2m-4,在實(shí)踐中應(yīng)該酌情考慮义屏。

在數(shù)組中靠汁，參考以下一個(gè)例子： 如果要在含n個(gè)數(shù)的數(shù)組array中找value值的索引

 1.普通寫法：
        for (int i = 0; i < n; ++i) {
            if (value == array[i])
                return i;
        }


    2.使用哨兵：
        array[n] = value;
        for (int i = 0;; i++) {
            if (value == array[i]) {
                if (i != n)
                    return i;
            }
        }

可以看使用哨兵比普通寫法節(jié)省了每次 i<n 的耗時(shí)，而這個(gè)消耗會(huì)隨著n的增大而增大

而在鏈表中闽铐，單鏈表在插入和刪除時(shí)蝶怔，需要修改前驅(qū)結(jié)點(diǎn)的后繼指針，這就形成了“鄰居依賴”兄墅，鏈表中第一個(gè)元素沒(méi)有前驅(qū)結(jié)點(diǎn)踢星，如果沒(méi)有特殊處理，在插入和刪除第一個(gè)結(jié)點(diǎn)時(shí)隙咸，就會(huì)出錯(cuò)沐悦。

所以我們可以申請(qǐng)一個(gè)頭結(jié)點(diǎn)，作為原本的第一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)扎瓶，問(wèn)題也就解決了所踊。但是在這種方式中，我們要插入或者刪除一個(gè)結(jié)點(diǎn)時(shí)概荷，如果此時(shí)要知道它的前驅(qū)結(jié)點(diǎn)地址，這往往是麻煩的碌燕。

image.png

如上圖所示误证，在單鏈表中第一個(gè)結(jié)點(diǎn)是哨兵結(jié)點(diǎn)继薛，它的item域是沒(méi)有確切意義的，而之后的item為5的結(jié)點(diǎn)才是鏈表中第一個(gè)元素愈捅，通過(guò)設(shè)置哨兵結(jié)點(diǎn)可以極大的簡(jiǎn)化對(duì)鏈表操作的邏輯遏考，使得代碼顯得簡(jiǎn)潔，下一節(jié)是一個(gè)基于哨兵結(jié)點(diǎn)的單鏈表蓝谨，其中具備了一些單鏈表常見(jiàn)操作灌具，同時(shí)實(shí)現(xiàn)了一些對(duì)鏈表的特殊操作（常見(jiàn)于面試題中）

另一個(gè)方式，也是我更喜歡的方式譬巫，是申請(qǐng)一個(gè)尾結(jié)點(diǎn)咖楣，作為原本最后一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)。

要?jiǎng)h除某個(gè)元素時(shí)芦昔，我們不刪除當(dāng)前這個(gè)結(jié)點(diǎn)诱贿，而是用后繼結(jié)點(diǎn)的數(shù)據(jù)覆蓋當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再刪除后繼結(jié)點(diǎn)咕缎。這種方式珠十，不需要訪問(wèn)前驅(qū)結(jié)點(diǎn)，也就解決了獲取前驅(qū)結(jié)點(diǎn)的困難凭豪。插入元素分為兩種情況：如果我們要在當(dāng)前節(jié)點(diǎn)后插入焙蹭，那么直接創(chuàng)建新結(jié)點(diǎn)，然后更改當(dāng)前節(jié)點(diǎn)的后繼與新結(jié)點(diǎn)的后繼結(jié)點(diǎn)就可以了嫂伞；如果我們要在當(dāng)前節(jié)點(diǎn)前插入孔厉，由于需要修改當(dāng)前節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼指針是比較麻煩的，可以新建一個(gè)值是當(dāng)前節(jié)點(diǎn)值的結(jié)點(diǎn)末早，然后把新結(jié)點(diǎn)的后繼指針指向當(dāng)前節(jié)點(diǎn)的后繼結(jié)點(diǎn)烟馅，修改當(dāng)前節(jié)點(diǎn)的后繼指針，同時(shí)修改當(dāng)前節(jié)點(diǎn)的值為新結(jié)點(diǎn)的原值然磷。
（注意：因?yàn)樯婕暗綌?shù)據(jù)的拷貝郑趁，如果結(jié)點(diǎn)的數(shù)據(jù)類型不是基本類型，而是引用數(shù)據(jù)類型姿搜，需要注意深淺拷貝的問(wèn)題）

對(duì)于雙向鏈表寡润，我們知道為了能夠在更快的在頭部和尾部分別進(jìn)行插入刪除操作（可以實(shí)現(xiàn)雙端隊(duì)列）而不需要遍歷鏈表，需要引入指向尾部的指針舅柜，觀察下圖中的情況

image.png

從上圖可以看出一個(gè)問(wèn)題梭纹，last結(jié)點(diǎn)有時(shí)指向哨兵結(jié)點(diǎn)，有時(shí)指向?qū)嶋H結(jié)點(diǎn)致份。這會(huì)導(dǎo)致特殊情況的出現(xiàn)变抽，比如在進(jìn)行addFirst操作時(shí)，last指向哨兵結(jié)點(diǎn)時(shí)插入后需要將last往后移動(dòng)一個(gè)，而第二張圖指向?qū)嶋H結(jié)點(diǎn)時(shí)在頭部插入結(jié)點(diǎn)后并不需要改變last指針绍载。這時(shí)需要在尾部后也引入一個(gè)哨兵結(jié)點(diǎn)诡宗，以使其一致。相應(yīng)示意圖如下：

image.png

但這樣一來(lái)一個(gè)雙向鏈表中击儡，就需要2個(gè)哨兵結(jié)點(diǎn)塔沃，我們做一下改進(jìn)，用一個(gè)哨兵結(jié)點(diǎn)實(shí)現(xiàn)
我們將雙向鏈表升級(jí)為循環(huán)雙向鏈表阳谍，讓哨兵結(jié)點(diǎn)指向頭結(jié)點(diǎn)蛀柴，item中不存內(nèi)容，當(dāng)為空鏈表時(shí)矫夯，使哨兵結(jié)點(diǎn)的前驅(qū)和后繼指針都指向自身

image.png

當(dāng)不為空鏈表時(shí)鸽疾，哨兵結(jié)點(diǎn)與第一個(gè)元素（實(shí)際為第二個(gè)結(jié)點(diǎn)）和最后一個(gè)結(jié)點(diǎn)鏈接在一起树姨，最后結(jié)點(diǎn)的后繼指針與哨兵結(jié)點(diǎn)的前驅(qū)指針相互指向?qū)Ψ?/p>

image.png

一個(gè)基于哨兵結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)

public class MyLinkedList<E extends Comparable> {
    // 結(jié)點(diǎn)類
    static class Node<E> {
        
        private E item;
        private Node<E> next;
        Node(){}
        Node(E element) {
            this.item = element;
        }

        public void setItem(E item) {
            this.item = item;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }

        public E getItem() {
            return item;
        }

        public Node<E> getNext() {
            return next;
        }
    }
    // 鏈表的第一個(gè)結(jié)點(diǎn),作為哨兵結(jié)點(diǎn)抚岗，不存放實(shí)際內(nèi)容，
    // 如果不使用哨兵結(jié)點(diǎn)帮寻，應(yīng)在各種鏈表操作中對(duì)其正常初始化和賦值
    private Node<E> sentry=new Node<>();

    public MyLinkedList() {
        
    }

    /**
     * 1. 判斷鏈表是否為空
     */
    public boolean isEmpty() {
        return sentry.next == null;
    }

    /**
     * 2. 返回鏈表長(zhǎng)度
     * @return 鏈表長(zhǎng)度
     */
    public int size() {
        return size(sentry);
    }

    /**
     * 3. 返回當(dāng)前節(jié)點(diǎn)后的結(jié)點(diǎn)數(shù)
     * @param head 當(dāng)前節(jié)點(diǎn)
     * @return head 結(jié)點(diǎn)之后的結(jié)點(diǎn)數(shù)
     */
    public static <E> int size(Node<E> head) {
        Node<E> temp = head.next;
        int size = 0;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 4. 正向遍歷鏈表
     */
    public void printList() {
        Node<E> temp = sentry.next;
        while (temp != null) {
            System.out.println(temp.item);
            temp = temp.next;
        }
    }

    /**
     * 5. 反向遍歷鏈表
     * 因?yàn)橐聪虮闅v鏈表旺订，考慮使用遞歸弄企，因?yàn)檫f歸調(diào)用棧既是一個(gè)天然的先入后出的隊(duì)列
     */
    public void printListReverse() {
        Node<E> temp = sentry.next;
        printListReverse(temp);
    }

    /**
     * 反向輸出當(dāng)前節(jié)點(diǎn)及之后的結(jié)點(diǎn)值
     * @param e
     */
    private void printListReverse(Node<E> e) {
        if (e != null) {
            printListReverse(e.next);
            System.out.println(e.item);
        }
    }

    /**
     * 6. 鏈表頭部添加節(jié)點(diǎn)
     * 如果頭結(jié)點(diǎn)為空，新加結(jié)點(diǎn)就是頭結(jié)點(diǎn)
     * 如果頭結(jié)點(diǎn)不為空区拳，則新加結(jié)點(diǎn)的next就是頭結(jié)點(diǎn)拘领，并且將頭結(jié)點(diǎn)設(shè)置為新加結(jié)點(diǎn)
     * 這里使用哨兵結(jié)點(diǎn)簡(jiǎn)化邊界條件
     * @param e <E> 要插入的結(jié)點(diǎn)值
     */
    public void addFirst(E e) {
        // 這里我們使用哨兵后，不需要對(duì)空鏈表進(jìn)行特殊處理
        Node<E> newNode = new Node<E>(e);
        newNode.next=sentry.next;
        sentry.next=newNode;
        
//     第一個(gè)結(jié)點(diǎn)不是哨兵結(jié)點(diǎn)時(shí)樱调，代碼如下：
//       Node<E> temp = sentry;
//       Node<E> newNode = new Node<E>(e, null);
//
//       if (temp == null) {
//           sentry = newNode;
//       }
//       else {
//           newNode.next = temp;
//           sentry = newNode;
//       }
    }

    /**
     * 7. 鏈表尾部添加節(jié)點(diǎn)
     * 直接找到最后一個(gè)節(jié)點(diǎn)约素，添加到最后一個(gè)節(jié)點(diǎn)的next
     * 特殊情況：如果鏈表長(zhǎng)度為0，直接令first為新插入節(jié)點(diǎn)
     * 引入哨兵節(jié)點(diǎn)處理特殊情況笆凌，簡(jiǎn)化邊界條件
     * @param e <E> 要插入的結(jié)點(diǎn)值
     */
    public void addLast(E e) {
        Node<E> newNode = new Node<E>(e);
        Node<E> current=sentry;
        while (current.next!=null) {
            current=current.next;
        }
        current.next=newNode;
//       第一個(gè)結(jié)點(diǎn)不是哨兵結(jié)點(diǎn)時(shí)圣猎，代碼如下：
//       Node<E> temp = sentry;
//       Node<E> newNode = new Node<E>(e, null);
//       if (temp == null) {
//            sentry = newNode;
//       }
//       else {
//            while (temp.next != null) {
//                temp = temp.next;
//            }
//            temp.next = newNode;
//       }
    }

    /**
     * 8. 鏈表按索引位置插入新結(jié)點(diǎn)
     * @param index 需要插入的結(jié)點(diǎn)位置，當(dāng)鏈表長(zhǎng)度為n時(shí)乞而，合法范圍為1~n+1
     * @param insertValue 需要插入的結(jié)點(diǎn)值
     */
    public boolean addNodeByIndex(int index, E insertValue) {
        if(insertValue==null){
            throw new IllegalArgumentException("空結(jié)點(diǎn)值送悔！");
        }
        if (index < 1 || index > size() + 1) {
            System.out.println("插入的位置不合法。");
            return false;
        }
        int count=1;
        Node<E> newNode = new Node<>(insertValue);
        Node<E> previous= sentry;
        while (count<index) {
            
            previous = previous.next;
            count++;
        }
        Node<E> current=previous.next;
        newNode.next=current;
        previous.next=newNode;
        return true;
        
        

    }

    /**
     * 9. 指定值的后面添加節(jié)點(diǎn)
     * 如果鏈表中已經(jīng)有了重復(fù)的值爪模，以排在最前面的為準(zhǔn).
     * 如果插入成功欠啤，則返回true
     * 如果插入失敗，則返回false
     * 特殊情況：
     * 1. 如果鏈表是空的屋灌，直接返回false
     * 2. 如果兩個(gè)參數(shù)有NULL值洁段，直接返回false
     * 以下幾個(gè)類似方法采用相同規(guī)則
     * @param aimValue <E>目標(biāo)結(jié)點(diǎn)值
     * @param insertValue <E>新插入的結(jié)點(diǎn)值
     * @return 返回插入是否成功
     */
    public boolean addAfter(E aimValue, E insertValue) {
        if(aimValue==null||insertValue==null)
            return false;
        Node<E> temp = sentry.next;
        while (temp != null) {
            if (temp.item.equals(aimValue)) {
                Node<E> newNode = new Node<E>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                return true;
            }
            else {
                temp = temp.next;
            }
        }
        return false;
       
    }

    /**
     * 10. 所有指定值后面添加節(jié)點(diǎn)
     * @param aimValue <E>目標(biāo)結(jié)點(diǎn)值
     * @param insertValue <E>新插入的結(jié)點(diǎn)值
     * @return 返回插入的結(jié)點(diǎn)數(shù)
     */
    public int addAftereAll(E aimValue, E insertValue) {
        if(aimValue==null||insertValue==null)
            return 0;
        // 插入值的個(gè)數(shù)
        int count = 0;
        Node<E> temp = sentry.next;
        while (temp != null) {
            if (temp.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                count++;
                // 由于是在temp后面加了一個(gè)指定值，所以要令temp = temp.next.next;
                temp = temp.next.next;
            }
            else {
                temp = temp.next;
            }
        }
        return count;
        
    }

    /**
     * 11. 指定值前面添加節(jié)點(diǎn)
     * @param aimValue <E>目標(biāo)結(jié)點(diǎn)值
     * @param insertValue <E>新插入的結(jié)點(diǎn)值
     * @return 返回插入是否成功
     */
    public boolean addBefore(E aimValue, E insertValue) {
        if(aimValue==null||insertValue==null)
            return false;
        // 假設(shè)我們要在A前插入B共郭，通過(guò)檢測(cè)X.next是否為A來(lái)獲取A的前驅(qū)結(jié)點(diǎn)祠丝，顯然這是一種可行方案
        // 但如果我們傳入的不是E疾呻，而是裝載E的Node，這種方案就不可以接受了
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                return true;
            }
            else {
                temp = temp.next;
            }
        }
//      這里選擇通過(guò)修改當(dāng)前節(jié)點(diǎn)值的方式插入,如果傳入的是一個(gè)在鏈表中的結(jié)點(diǎn)纽疟，
//      連從頭結(jié)點(diǎn)遍歷至所需結(jié)點(diǎn)都省了(當(dāng)然這里并不是)
//        Node temp1=sentry.next;
//        while (temp1 != null) {
//            if (temp1.item.equals(aimValue)) {
//                Node<E> newNode = new Node<>(temp1.item);
//                newNode.next = temp1.next;
//                temp1.next = newNode;
//                temp1.item=insertValue;
//                return true;
//            }
//            else {
//                temp = temp.next;
//            }
//        }
        return false;
    }

    /**
     * 12. 所有指定值前面添加節(jié)點(diǎn)
     * 返回添加的次數(shù)
     * @param aimValue <E>目標(biāo)結(jié)點(diǎn)值
     * @param insertValue <E>新插入的結(jié)點(diǎn)值
     * @return 返回插入結(jié)點(diǎn)的個(gè)數(shù)
     */
    public int addBeforeAll(E aimValue, E insertValue) {
        // 如果頭結(jié)點(diǎn)為空罐韩，表示一定沒(méi)有插入的位置憾赁，直接返回0污朽。
        if(aimValue==null||insertValue==null)
            return 0;
        // 插入值的個(gè)數(shù)
        int count = 0;
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                count++;
                // 由于是在temp后面加了一個(gè)指定值，所以需要把原來(lái)temp.next結(jié)點(diǎn)設(shè)為新的temp龙考，這樣邏輯才正確
                temp = newNode.next;
            }
            else {
                temp = temp.next;
            }
        }
        return count;
    }

    /**
     * 13. 返回鏈表的頭結(jié)點(diǎn)
     * @return 頭結(jié)點(diǎn)
     */
    public Node<E> head() {
        return sentry.next;
    }

    /**
     * 14. 返回鏈表的尾結(jié)點(diǎn),注意不要返回哨兵結(jié)點(diǎn)
     * @return 尾結(jié)點(diǎn)
     */
    public Node<E> tail() {
        Node<E> temp = sentry;
        while (temp.next != null) {
            temp = temp.next;
        }
        if(temp==sentry)
            return null;
        return temp;
        
    }

    

    /**
     * 15. 刪除指定值一個(gè)節(jié)點(diǎn)
     * 特殊情況：
     * 如果鏈表長(zhǎng)度為0,或者aimValue為null蟆肆，直接返回false，
     * @return 成功返回true,失敗返回false
     */
    public boolean removeOneNode(E aimValue) {
        if (sentry.next == null || aimValue == null) {
            return false;
        }
        
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                temp.next = temp.next.next;
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * 16. 刪除指定值所有節(jié)點(diǎn),返回刪除的個(gè)數(shù)
     * @return 返回刪除的結(jié)點(diǎn)個(gè)數(shù)
     */
    public int removeAllNode(E aimValue) {
        if (sentry.next == null || aimValue == null) {
            return 0;
        }
        int count = 0;
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                temp.next = temp.next.next;
                count++;
            }
            else {
                temp = temp.next;
            }
        }
        return count;
    }

    /**
     * 17. 鏈表按索引位置刪除結(jié)點(diǎn)
     * @param index 位置索引晦款，合法范圍為1~n
     * @return 返回刪除是否成功
     */
    public boolean removeNodeByIndex(int index){
        if(sentry.next==null){
            throw new IllegalArgumentException("空鏈表炎功！");
        }
        if (index < 1 || index > size()) {
            System.out.println("刪除的位置不合法。");
            return false;
        }
        int count=1;
        Node<E> previous= sentry;
        while (count<index) {

            previous = previous.next;
            count++;
        }
        Node<E> current=previous.next.next;
        previous.next=current;
        return true;
    }
}

高效的雙向鏈表

image.png

image.png

image.png

NULL用0表示

考慮鏈表第一個(gè)元素x.ptrdiff =NULL ^ x.next = x.next缓溅，即表頭存的指針值和普通雙向鏈表表頭的next指針相同

中間所有元素x.ptrdiff= x.prev ^ x.next

考慮鏈表最后一個(gè)元素x.ptrdiff = x.prev ^ NULL = x.prev蛇损，即鏈表最后一個(gè)元素存的指針和普通雙向鏈表表尾的prev指針相同

我們知道第一個(gè)元素的next指針，中間元素的next指針可以通過(guò)前一個(gè)元素的ptrdiff和當(dāng)前元素的ptrdiff異或計(jì)算獲得坛怪，這就為前序遍歷創(chuàng)造了可能

我們知道最后一個(gè)元素的prev指針淤齐，中間元素的prev指針可以通過(guò)當(dāng)前元素的ptrdiff和后一個(gè)元素的ptrdiff異或計(jì)算獲得，這就為后續(xù)遍歷創(chuàng)造了可能

總之袜匿，ptrdiff = prev ^ next, NULL = 0致使鏈表頭元素和尾元素ptrdiff值具有了特殊性更啄，這正是此種表示的精妙之處，節(jié)省了O(n)的空間開(kāi)銷居灯，但增加了運(yùn)算開(kāi)銷（位運(yùn)算）祭务，計(jì)算機(jī)執(zhí)行位運(yùn)算具有速度優(yōu)勢(shì)。

此種情況下怪嫌，如果想要翻轉(zhuǎn)鏈表就變得異常容易义锥，只需要將鏈表的頭尾指針交換即可。

由于java中沒(méi)有指針運(yùn)算岩灭，我們無(wú)法通過(guò)指針?lè)奖愕墨@取結(jié)點(diǎn)地址從而獲取結(jié)點(diǎn)信息拌倍，所以這里了解一下就好了

松散鏈表

與數(shù)組相比，鏈表給定一個(gè)位置的結(jié)點(diǎn)情況下川背，插入和刪除只需要的時(shí)間開(kāi)銷贰拿，但如果只給定位置(或者所需結(jié)點(diǎn)的要求)，不給定結(jié)點(diǎn)熄云，那么鏈表就需要從表頭遍歷至所需結(jié)點(diǎn)膨更，時(shí)間開(kāi)銷為，下面介紹一種單向鏈表的簡(jiǎn)單變形——松散鏈表缴允。

松散鏈表的每個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)元素（簡(jiǎn)稱為塊）荚守，每一塊中所有結(jié)點(diǎn)由循環(huán)鏈表連在一起珍德。可以理解為松散鏈表是由多個(gè)塊用單向鏈表方式組成的矗漾，而每個(gè)塊內(nèi)部是循環(huán)鏈表

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

1. 在塊的實(shí)現(xiàn)上，我們不采用循環(huán)鏈表敞贡，而選擇使用數(shù)組泵琳，因?yàn)閿?shù)組的內(nèi)存連續(xù)性，如果合理安排數(shù)組大小誊役，使每個(gè)數(shù)組（也就是塊）的大小不超過(guò)一個(gè)緩存行（最好是一個(gè)緩存行）获列，就可以滿足在時(shí)間上的優(yōu)勢(shì)（原因如下，其實(shí)也是顯而易見(jiàn)的）

   
   
   image.png

2. 如以下所論述的：
   When constructing unrolled linked lists, apparently implementations will try to generally leave space in the nodes; when you try to insert in a full node, you move half the elements out. Thus, at most one node will be less than half full. And according to what I can find (I haven't done any analysis myself), if you insert things randomly, nodes tend to actually be about three-quarters full, or even fuller if operations tend to be at the end of the list.
   簡(jiǎn)單翻譯一下：
   在構(gòu)造松散鏈表的實(shí)現(xiàn)時(shí)蛔垢，通常會(huì)對(duì)每個(gè)塊留有足夠的空間击孩。當(dāng)你試圖添加一個(gè)元素到一個(gè)滿塊中，會(huì)將這個(gè)塊一半的元素移出到別的塊鹏漆。因此巩梢，最多只有在開(kāi)始階段時(shí)一個(gè)塊元素少于一半容量。并且在隨機(jī)插入的情況下艺玲，每個(gè)塊大概會(huì)有四分之一是空的括蝠。

經(jīng)查閱資料，實(shí)際上板驳，在scala中就有一個(gè)基于松散鏈表的基本原理的實(shí)現(xiàn) UnrolledBuffer
https://www.scala-lang.org/api/2.11.7/index.html#scala.collection.mutable.UnrolledBuffer
我們完全可以通過(guò)使用一個(gè)item為Object數(shù)組的單鏈表又跛，采用和Arraylist類似的實(shí)現(xiàn)

class UnrollLinkList<T> {
    class UnrollNode {
        UnrollNode next; // 下一個(gè)塊
        int num_elements; // 塊中的實(shí)際元素個(gè)數(shù)
        Object array[]; // 存儲(chǔ)元素的數(shù)組

        // Constructor 
        public UnrollNode(int n)
        {
            next = null;
            num_elements = 0;
            array = new Object[n];
        }
    }
    private UnrollNode start_pos; // 第一個(gè)塊   
    private UnrollNode end_pos; // 最后一個(gè)塊
    int size_node;  // 每個(gè)塊可容納的元素個(gè)數(shù)
    int nNode;  // 元素總個(gè)數(shù)

    // Parameterized Constructor 
    UnrollLinkList(int capacity)
    {
        start_pos = null;
        end_pos = null;
        nNode = 0;
        size_node = capacity ;
    }

    /**
     * 插入的邏輯如下（尾插法）：
     * 1. 檢查第一個(gè)塊是否為空，為空則在第一個(gè)塊中分配相應(yīng)數(shù)組若治，并為數(shù)組第一個(gè)元素賦值同時(shí)讓最后一個(gè)塊指向第一個(gè)快
     * 2. 檢查最后一個(gè)塊是否還能容納新元素慨蓝，如果可以則在最后一個(gè)塊的數(shù)組中第一個(gè)空閑位置插入
     * 3. 如果不能容納新元素，則新建一個(gè)塊端幼，把原最后一個(gè)塊后一半元素拷貝入新塊中礼烈，同時(shí)更改原最后一個(gè)塊有效值的索引
     *    將新元素置入新塊，再把新塊置為最后一個(gè)塊
     * @param num
     */
    
     
    void Insert(T num)
    {
        nNode++;

        // 1.
        if (start_pos == null) {
            start_pos = new UnrollNode(size_node);
            start_pos.array[0] = num;
            start_pos.num_elements++;
            end_pos = start_pos;
            return;
        }

        // 2.
        if (end_pos.num_elements  < size_node) {
            end_pos.array[end_pos.num_elements] = num;
            end_pos.num_elements++;
        }

        // 3.
        else {
            UnrollNode node_pointer = new UnrollNode(size_node);
            int j = 0;
            for (int i = end_pos.num_elements / 2 + 1;
                 i < end_pos.num_elements; i++)
                node_pointer.array[j++] = end_pos.array[i];

            node_pointer.array[j++] = num;
            node_pointer.num_elements = j;
            end_pos.num_elements = end_pos.num_elements / 2 + 1;
            end_pos.next = node_pointer;
            end_pos = node_pointer;
        }
    }

    // Display the Linked List 
    void display()
    {
        System.out.print("\nUnrolled Linked List = ");
        System.out.println();
        UnrollNode pointer = start_pos;
        while (pointer != null) {
            for (int i = 0; i < pointer.num_elements; i++)
                System.out.print(pointer.array[i] + " ");
            System.out.println();
            pointer = pointer.next;
        }
        System.out.println();
    }
}

顯然想要在存儲(chǔ)空間均勻分配與空間的利用率上獲得好的效果婆跑，會(huì)有更復(fù)雜的增刪邏輯此熬，這里只做了解，下一種是更值得我們耗費(fèi)精力學(xué)習(xí)的鏈表結(jié)構(gòu)

跳躍鏈表

跳躍鏈表是一種可以替代平衡二叉樹(shù)的結(jié)構(gòu)滑进，與平衡二叉樹(shù)相比犀忱，這種鏈表可以迅速執(zhí)行搜索，插入和刪除操作扶关。它的平衡是數(shù)學(xué)概率的平衡而非平衡二叉樹(shù)那樣嚴(yán)格的平衡阴汇。其實(shí)這種鏈表本質(zhì)上只是普通的單鏈表上，加入了一些指針使其能夠跳過(guò)鏈表中某些元素节槐。它采用隨機(jī)數(shù)生成器來(lái)制定某些決策搀庶。
對(duì)于有序鏈表而言拐纱，其搜索，插入和刪除都需要耗費(fèi)級(jí)別的時(shí)間哥倔，因?yàn)樾枰阉薪Y(jié)點(diǎn)依次掃描才能找到相應(yīng)結(jié)點(diǎn)秸架，如果能以較大的步伐來(lái)邁進(jìn)，那么就可以顯著減少掃描的開(kāi)銷咆蒿，這正是跳躍鏈表的意義所在东抹。需要注意的是，AVL的實(shí)現(xiàn)一般都比較復(fù)雜蜡秽，插入/刪除元素可能涉及對(duì)整個(gè)樹(shù)結(jié)構(gòu)的修改府阀，特別是并發(fā)環(huán)境下，通常需要全局鎖來(lái)保證AVL的線程安全芽突，而跳躍鏈表在這方面性能要優(yōu)秀很多。

image.png

image.png

image.png

用數(shù)學(xué)方法分析董瞻，如果在L1基礎(chǔ)上寞蚌，還有一層L2，設(shè)L1長(zhǎng)度為n钠糊，L2長(zhǎng)度為m挟秤，則復(fù)雜度可表示為（也就是L2的長(zhǎng)度加上L1被分割的一節(jié)的長(zhǎng)度），顯然當(dāng)時(shí)抄伍，取到最小值為（此時(shí)相當(dāng)于最普通的松散鏈表）
同理艘刚，如果加上一層L3，復(fù)雜度為截珍，到第k層攀甚，復(fù)雜度為，我們?nèi)?img class="math-inline" src="https://math.jianshu.com/math?formula=k%3D%5Clog%20n" alt="k=\log n" mathimg="1">時(shí)獲得最小值岗喉，

在敘述插入操作前秋度，我們應(yīng)該知道，跳躍表具有以下幾個(gè)必備的性質(zhì)：

• 最底層是一個(gè)包含所有節(jié)點(diǎn)的有序鏈表
• 每一層都是一個(gè)有序的鏈表钱床，由高向低結(jié)點(diǎn)數(shù)遞減
• 每層的每個(gè)節(jié)點(diǎn)都有兩個(gè)指針荚斯，一個(gè)指向右側(cè)節(jié)點(diǎn)（沒(méi)有則為空），一個(gè)指向下層節(jié)點(diǎn)（沒(méi)有則為空）
• 每層鏈表的頭結(jié)點(diǎn)相同查牌，通過(guò)它可以遍歷整個(gè)鏈表（多數(shù)情況下使用哨兵結(jié)點(diǎn)）
• 如果一個(gè)結(jié)點(diǎn)在上面某一層出現(xiàn)事期，則它一定也出現(xiàn)在下面所有層中

image.png

注意紅線表示查找的過(guò)程

算法導(dǎo)論中，對(duì)插入策略的敘述如下：
對(duì)每個(gè)新添加的結(jié)點(diǎn)纸颜，采用類似拋硬幣的方法兽泣，各有二分之一的概率選擇使其升層，比如當(dāng)其從L1提升至L2時(shí)懂衩，繼續(xù)做隨機(jī)的檢測(cè)撞叨，直至檢測(cè)失敗為止金踪，此時(shí)，這個(gè)結(jié)點(diǎn)出現(xiàn)在level=k及以下所有層中牵敷，如果k大于最高層胡岔，則新建一層，之后我們從高向低枷餐，依次將結(jié)點(diǎn)插入入每層鏈表中
這種方式在數(shù)學(xué)上能保證其層數(shù)小于等于的概率在間

而刪除操作也很簡(jiǎn)單靶瘸，需要從左上方開(kāi)始查找直至找到相應(yīng)元素，讓后把這個(gè)結(jié)點(diǎn)以及其所有向下指向的結(jié)點(diǎn)全部刪除

在代碼實(shí)現(xiàn)上

image.png

想要真正理解跳躍表毛肋，參見(jiàn)ConcurrentSkipListMap的源碼解析

習(xí)題解答

image.png

image.png

image.png

image.png

image.png

image.png

image.png

上圖中怨咪，設(shè)環(huán)外有k步，快慢指針相遇在環(huán)中藍(lán)色delta位置處润匙，環(huán)的入口為紅色位置诗眨，環(huán)的長(zhǎng)度為R

必然相遇的證明
1、如果鏈表沒(méi)有環(huán)孕讳，那么快指針比慢指針先到達(dá)尾部（null)匠楚。
2、如果鏈表有環(huán)的話厂财，因?yàn)榭熘羔樧叩谋嚷羔樋煊蟛荆栽诃h(huán)中相遇的過(guò)程可以看作是快指針從環(huán)后邊追趕慢指針的過(guò)程。
用遞歸法證明璃饱，快慢指針一定會(huì)相遇：
（1)快指針與慢指針之間差一步与斤。此時(shí)繼續(xù)往后走，慢指針前進(jìn)一步荚恶，快指針前進(jìn)兩步撩穿，兩者相遇。
（2)快指針與慢指針之間差兩步裆甩。此時(shí)繼續(xù)往后走冗锁，慢指針前進(jìn)一步，快指針前進(jìn)兩步嗤栓，兩者之間相差一步冻河，轉(zhuǎn)化為第一種情況。
（3)快指針與慢指針之間差x步茉帅。此時(shí)繼續(xù)往后走叨叙，慢指針前進(jìn)一步，快指針前進(jìn)兩步堪澎，兩者之間相差(x+1-2)即x-1步擂错。重復(fù)這個(gè)過(guò)程，直到快指針和慢指針相遇樱蛤。
因此钮呀，此題得證剑鞍。所以快指針必然與慢指針相遇。

同時(shí)顯然快指針先進(jìn)環(huán)爽醋，慢指針后進(jìn)蚁署。
假設(shè)慢指針進(jìn)環(huán)那一刻快指針差m步能追上（0<= m < R），根據(jù)上邊結(jié)論蚂四，兩個(gè)指針走m次就會(huì)相遇了光戈。因?yàn)閙 < R，所以快指針在慢指針進(jìn)環(huán)那一刻最多比慢指針多繞一個(gè)圈遂赠。
也就是說(shuō)慢指針被追上時(shí)久妆，在環(huán)中沒(méi)有走完一圈。有等式
跷睦，等號(hào)左邊是滿指針的兩倍距離筷弦，等號(hào)右邊是快指針的距離（x表示繞了多少正整數(shù)圈）
即，顯然如果環(huán)不存在送讲，則等式不成立奸笤，R至少為1才能使等號(hào)成立（為1時(shí)相當(dāng)于尾結(jié)點(diǎn)指向自身）

image.png

image.png

image.png

正如上文分析的那樣，從處走步哼鬓，正好等于在環(huán)的入口處走步回到環(huán)的入口，而通過(guò)快慢指針相遇可以求出來(lái)边灭，未知的k正好可以通過(guò)重新設(shè)定位置和速度再次相遇而求出异希，此時(shí)兩者相遇位置正好是環(huán)的入口處

image.png

image.png

image.png

原地的鏈表迭代逆置參考如下圖

image.png

image.png

方法2：頭插法逆置
分為兩種情況：①鏈表為空或者鏈表中僅有一個(gè)節(jié)點(diǎn)，直接返回pHead ②鏈表中有多個(gè)節(jié)點(diǎn)時(shí)：將pHead后面的節(jié)點(diǎn)依次插入到頭結(jié)點(diǎn)的后面绒瘦，這樣顯然需要一個(gè)新的鏈表結(jié)構(gòu)存儲(chǔ)称簿，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)
方法3：遞歸逆置

 Node reverse3(Node head) {
        //遞歸出口
        //注意這里加入對(duì)head.next==null的判斷惰帽，防止下文中的head.next.next出現(xiàn)空指針異常
        if (head == null || head.next == null)
            return head;
        //遞歸子情況
        Node pre = reverse3(head.next);
        head.next.next = head;  // 這一步會(huì)造成環(huán)
        head.next = null;  // 這一步是為了斷開(kāi)環(huán)
        return pre;
    }

image.png

image.png

ps:在帶有指針的語(yǔ)言體系中憨降，還可以通過(guò)三指針?lè)?/p>

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png