代碼GitHub地址

鏈表概述

• 數(shù)組和鏈表都是線性存儲結(jié)構(gòu)的基礎(chǔ)實(shí)現(xiàn)，棧和隊(duì)列都是線性存儲結(jié)構(gòu)的應(yīng)用

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

說起鏈表必須說一下數(shù)組：數(shù)組是一種連續(xù)存儲線性結(jié)構(gòu)竿音，元素類型相同舔痪，大小相等

數(shù)組優(yōu)勢：存取速度快。

數(shù)組劣勢：

1. 事先必須知道數(shù)組的長度
2. 空間通常是有限制的
3. 需要大塊連續(xù)的內(nèi)存塊
4. 插入刪除元素的效率很低

鏈表優(yōu)缺點(diǎn)

鏈表是離散存儲線性結(jié)構(gòu)

n個(gè)節(jié)點(diǎn)離散分配，彼此通過指針相連歉秫，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)籽暇，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)温治，首節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒有后續(xù)節(jié)點(diǎn)戒悠。

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

1. 空間沒有限制
2. 插入刪除元素很快

鏈表缺點(diǎn)：

1. 節(jié)點(diǎn)的獲取很慢

鏈表分類

• 對于鏈表熬荆，如果用數(shù)組實(shí)現(xiàn)。那即是靜態(tài)鏈表
• 鏈表分好幾類：
  • 有單向鏈表绸狐，
    • 一個(gè)節(jié)點(diǎn)有一個(gè)指針域?qū)傩月笨遥赶蚱浜罄^節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)為NULL寒矿。
  • 雙向鏈表
    • 一個(gè)節(jié)點(diǎn)兩個(gè)指針域?qū)傩酝涣眨謩e指向其前驅(qū)，后繼節(jié)點(diǎn)
  • 循環(huán)鏈表
    • 相比于單向鏈表符相，尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)為鏈表的首節(jié)點(diǎn)拆融。
  • 雙向循環(huán)鏈表
    • 能通過任何一個(gè)節(jié)點(diǎn)找到其他所有節(jié)點(diǎn)，相比于雙向鏈表啊终，把最后一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向了第一個(gè)節(jié)點(diǎn)镜豹，進(jìn)而形成環(huán)式循環(huán)。

鏈表需要注意的點(diǎn)

• 鏈表需要相同的數(shù)據(jù)類型
• 鏈表的處理方式都是先取代蓝牲，后目的逛艰。比如刪除鏈?zhǔn)骄€性表的某個(gè)節(jié)點(diǎn)的流程，先取代delete point使它的前驅(qū)節(jié)點(diǎn)指向它的后繼節(jié)點(diǎn)搞旭，這樣就完成了取代散怖。然后再free()掉這個(gè)節(jié)點(diǎn)菇绵，這樣就達(dá)到了目的。再比如加入某個(gè)節(jié)點(diǎn)镇眷，先使add point指向add index要加入處的后繼節(jié)點(diǎn)咬最，這即取代。然后再使add index的前驅(qū)節(jié)點(diǎn)指向add point欠动。
• 操作一個(gè)鏈表只需要知道它的頭指針就可以做任何操作了

解題步驟：

1. 先考慮特殊情況永乌，邊緣值
2. 進(jìn)入退出循環(huán)時(shí)需要找準(zhǔn)條件，考慮清楚退出循環(huán)時(shí)所需要的變量的終值是多少具伍，方便使用
3. 審視全局翅雏，帶正確的值判斷是否AC

控制選擇的節(jié)點(diǎn)

int i = 1;

while (i < index) {
    headNode = headNode.getNextNode();
    i++;
}

這段代碼意義即，從初始化i=0開始人芽，如果要插入節(jié)點(diǎn)到第i個(gè)的位置望几。那么我們就一定需要找到第i-1個(gè)節(jié)點(diǎn)。所以現(xiàn)在我們目標(biāo)明確了萤厅，要找第i-1個(gè)節(jié)點(diǎn)橄抹。
因?yàn)檠h(huán)的結(jié)束條件是由i控制的，如果我們使變量i原本從0開始計(jì)數(shù)++到i-1結(jié)束惕味。跳過的是i個(gè)元素楼誓。這樣就把我們需要的第i-1節(jié)點(diǎn)跳過了。而我們要想取到它名挥，很明顯我們需要讓循環(huán)少進(jìn)行一次疟羹。
為了邏輯清晰，循環(huán)判斷條件不應(yīng)改變禀倔。那么我們就需要把i的初始值改為1榄融，而非原先的0。

鏈表操作

目錄：

• 遍歷
• 查找
• 清空
• 銷毀
• 求長度
• 排序
• 刪除節(jié)點(diǎn)
• 插入節(jié)點(diǎn)

Github - 單鏈表代碼地址 - 歡迎star

添加數(shù)據(jù)到鏈表中

• 那么無疑是找到尾節(jié)點(diǎn)插入即可
  while(tempNode.getNextNode()!=null)當(dāng)退出循環(huán)時(shí)蹋艺，那么就定位到了后繼節(jié)點(diǎn)為NULL的節(jié)點(diǎn)即尾節(jié)點(diǎn)剃袍。

遍歷鏈表

• 從頭結(jié)點(diǎn)開始輸出黄刚，直到尾節(jié)點(diǎn)捎谨。
  while(tempNode!=null)那么退出循環(huán)時(shí)即所有節(jié)點(diǎn)全部輸出。

給定位置插入節(jié)點(diǎn)到鏈表中

• 鏈表插入的題要看清題意憔维。是要往第i個(gè)位置插入涛救，還是往索引為i的位置插入。在同樣具有虛擬頭結(jié)點(diǎn)的前提下业扒，兩者直接決定了i的初始值检吆。
• 因?yàn)橐付ㄎ恢貌迦牍?jié)點(diǎn)。比如2143要往第3個(gè)位置插程储，那么即插到1,4中間蹭沛。 所以要往哪個(gè)位置插那么必須找到他的前驅(qū)節(jié)點(diǎn)1臂寝。這也是我們前面所講的控制選擇的節(jié)點(diǎn)的使用場景。
• 如下進(jìn)入判斷條件中摊灭，如果起始條件是0的時(shí)候咆贬，那么需要注意，每進(jìn)入一次循環(huán)+1帚呼。那么它總共會進(jìn)入3次掏缎。0,1,2∶荷保可是循環(huán)中節(jié)點(diǎn)向下遍歷眷蜈。如果首次進(jìn)入循環(huán)的開始節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)而非頭結(jié)點(diǎn)的話即2。往后跳三次沈自，就會找到3節(jié)點(diǎn)酌儒，很明顯不是我們想要的。
• 所以我們應(yīng)該明白如果要插入到第10個(gè)位置酥泛，我們需要找到第九個(gè)節(jié)點(diǎn)今豆，那么循環(huán)起始從第一個(gè)開始的話，找到第九個(gè)需要進(jìn)循環(huán)8次退出循環(huán)時(shí)才是第9個(gè)節(jié)點(diǎn)柔袁。所以我們可以看出呆躲，要插到第10個(gè)位置我們需要循環(huán)得是8次而不是9次。
  • 我們知道如果i從0- i<10是10次捶索。即0-9那么我們可以控制i從i = 1開始插掂，這樣只使循環(huán)少了一次。那么另一次怎么減呢
  • 我們可以再通過使第一次進(jìn)入循環(huán)的節(jié)點(diǎn)是頭結(jié)點(diǎn)而不是第一個(gè)擁有實(shí)際value的節(jié)點(diǎn)開始腥例。這樣我們就可以使無用節(jié)點(diǎn)也占用一次循環(huán)辅甥，也就相當(dāng)于使循環(huán)次數(shù)-1了。

    index = 3;
    ----
    int i = 0;
    temp = headNode.getNextNode();
    while(i < index){
        tempNode = tempNode.getNextNode();
        i++;
    }
    
    int i = 1;
    temp = headNode;
    while(i < index){
        tempNode = tempNode.getNextNode();
        i++;
    }

• 然后接下承上燎竖，即要插入的這個(gè)節(jié)點(diǎn)Node.next = 4然后1.next = Node璃弄。切不可亂了順序，否則會丟失指針

獲取鏈表的長度

• 遍歷鏈表构回，聲明一個(gè)變量夏块，每遍歷一個(gè)節(jié)點(diǎn)變量+1。

int i = 0;
tempNode = headNode.next;
while(tempNode!=null) {
    i++;
    tempNode = tempNode.next;
}

• 這里需要明白兩點(diǎn)纤掸。
  • 當(dāng)tempNode等于頭結(jié)點(diǎn)的時(shí)候脐供，我們可以想到這種情況會使循環(huán)多進(jìn)行一次。
  • 當(dāng)循環(huán)判斷條件while()借跪，判斷的不是tempNode!=null即當(dāng)前節(jié)點(diǎn)政己，而是tempNode.next!=null下一節(jié)點(diǎn)時(shí)。會使循環(huán)少進(jìn)行一次掏愁。
  • 這兩點(diǎn)很重要歇由，循環(huán)進(jìn)行多少次的掌控就在這幾點(diǎn)卵牍。

刪除給定位置的節(jié)點(diǎn)

• 和從指點(diǎn)位置插入點(diǎn)一樣。都是要找指定位置的前驅(qū)節(jié)點(diǎn)沦泌。
• 總共4個(gè)節(jié)點(diǎn)辽慕，我們要?jiǎng)h除第3個(gè)位置的節(jié)點(diǎn)。即需要找到第2個(gè)節(jié)點(diǎn)赦肃，進(jìn)入一次循環(huán)節(jié)點(diǎn)向后移一位溅蛉， 進(jìn)入節(jié)點(diǎn)時(shí)是第一個(gè)節(jié)點(diǎn)。那么我們需要進(jìn)循環(huán)一次即可他宛。那么即

int i = 1船侧；
while(i < 3){
    i++;
    temp = temp.next;
}

對鏈表進(jìn)行排序

• 冒泡排序
  • 雙層循環(huán)，外層節(jié)點(diǎn)起始位置第一節(jié)點(diǎn)temp = headNode.next厅各，退出條件temp != null镜撩。這是索引循環(huán)起始指向第一節(jié)點(diǎn)，最終從末尾節(jié)點(diǎn)跳出队塘。
  • 內(nèi)層循環(huán)袁梗，起始節(jié)點(diǎn)即第一節(jié)點(diǎn)nextNode = headNode.next，退出條件nextNode.next != null憔古，因?yàn)槊芭菔乔昂笤乇却笮〉?和第2比遮怜，第n-1和第n比。所以當(dāng)指到最后節(jié)點(diǎn)的時(shí)候就可以跳出鸿市。

找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

• 這個(gè)起始和正向找節(jié)點(diǎn)是一個(gè)概念锯梁，我們只要利用循環(huán)鏈表的思路變換數(shù)字即可。首先我們可以把鏈表看成一個(gè)首尾相連的循環(huán)結(jié)構(gòu)焰情。那么倒數(shù)第k個(gè)陌凳，即一個(gè)元素正數(shù)位置的絕對值加上倒數(shù)位置的絕對值比總數(shù)多1。比如6個(gè)數(shù)内舟，我們找倒數(shù)第二個(gè)合敦。倒數(shù)第2個(gè)也是正數(shù)第5個(gè)，2+5-1=6验游。所以我們要找一個(gè)數(shù)充岛，正向找無疑很方便，只需要(-k+1+總數(shù)) = 元素位置批狱。我們只需要對鏈表進(jìn)行排序后獲取該元素即可

/**
     * 找鏈表倒數(shù)第index個(gè)節(jié)點(diǎn)
     *
     * @param headNode
     * @param index
     * @return
     */
    public static int findNode(Node headNode, int index) {
        int listLength = listLength(headNode);
        index = -index;
        int trueIndex = (index + listLength + 1) % listLength;
        for (int i = 0; i < trueIndex; i++) {
            headNode = headNode.getNextNode();
        }
        return headNode.getValue();
    }

• 我們也可以用追隨節(jié)點(diǎn)辦法裸准，設(shè)立兩個(gè)節(jié)點(diǎn)展东。一個(gè)節(jié)點(diǎn)比另一個(gè)節(jié)點(diǎn)快k步赔硫。即先行節(jié)點(diǎn)走了k下，后行節(jié)點(diǎn)出發(fā)走第一下盐肃。當(dāng)后行節(jié)點(diǎn)跳出循環(huán)爪膊，那么先行節(jié)點(diǎn)必然是倒數(shù)第k個(gè)節(jié)點(diǎn)权悟。我們一般也用這種方法來找一個(gè)鏈表的幾等分點(diǎn)。如果找一個(gè)鏈表的三等分點(diǎn)推盛，我們給連個(gè)節(jié)點(diǎn)一個(gè)走三步一個(gè)走一步即可峦阁。

/**
     * 找倒數(shù)第k個(gè)節(jié)點(diǎn)|追點(diǎn)，簡潔寫法
     *
     * @param headNode
     * @return
     */
    public static int findNode3(Node headNode, int k) {
        Node tempNode = headNode;
        Node nextNode = null;
        int i = 0;
        while (tempNode != null) {
            i++;
            tempNode = tempNode.getNextNode();
            if (tempNode == null) {
                break;
            }
            if (i == k) {
                nextNode = headNode.getNextNode();
            } else if (i > k) {
                nextNode = nextNode.getNextNode();
            }
        }
        return nextNode.getValue();
    }

刪除鏈表重復(fù)數(shù)據(jù)

這里我用while循環(huán)寫的耘成，比較簡單而且簡潔榔昔。其實(shí)本質(zhì)上和冒泡排序的思路一樣，思考的時(shí)候用for循環(huán)的思路思考臨界條件即可瘪菌。非常簡單

• 雙重循環(huán)撒会，第一層循環(huán)是索引節(jié)點(diǎn)循環(huán)，循環(huán)進(jìn)入從第一個(gè)節(jié)點(diǎn)開始师妙，到尾節(jié)點(diǎn)跳出诵肛。
  • 內(nèi)循環(huán)，每進(jìn)入內(nèi)循環(huán)一層循環(huán)的時(shí)候把next節(jié)點(diǎn)賦予最新的外層索引值默穴。然后取該next節(jié)點(diǎn)的next節(jié)點(diǎn)值與索引節(jié)點(diǎn)的值進(jìn)行比較怔檩。向后循環(huán)

/**
 * 刪除重復(fù)元素,|參考別人的 O(n2)
 *
 * @param headNode
 */
  public static void removeDumplecateEle(Node headNode) {
        Node temp = headNode.getNextNode();
        Node next;
        while (temp != null) {
            next = temp;
            while (next.getNextNode() != null) {
                if (next.getNextNode().getValue() == temp.getValue()) {
                    next.setNextNode(next.getNextNode().getNextNode());
                } else {
                    next = next.getNextNode();
                }
            }
            temp = temp.getNextNode();
        }
    }

• hashtable做法。使鏈表上的每個(gè)節(jié)點(diǎn)插入到hashtable中蓄诽，插入前進(jìn)行判斷是否在hashtable中存在薛训。
  • 需要注意的是，hashtable在存儲的時(shí)候是將該值存到了鍵值的位置仑氛。value恒定給值许蓖，否則不方便遍歷。

/**
     * 刪除重復(fù)元素 hashtable| 空間開銷變大调衰，O(n)
     *
     * @param headNode
     */
    public static void removeDuplecate3(Node headNode) {
        Hashtable<Integer, Integer> hashtable = new Hashtable<Integer, Integer>();
        Node tempNode = headNode.getNextNode();
        while (tempNode != null) {
            if (!hashtable.containsKey(tempNode.getValue())) {
                hashtable.put(tempNode.getValue(), 1);
            }
            tempNode = tempNode.getNextNode();
        }
        // 打印
        for (Map.Entry<Integer, Integer> entryItem : hashtable.entrySet()
                ) {
            System.out.println(entryItem.getKey());
        }
    }

查詢鏈表的中間節(jié)點(diǎn)

• 兩個(gè)指針膊爪，一個(gè)走兩步，一個(gè)走一步嚎莉。同一起點(diǎn)出發(fā)米酬，拿先行節(jié)點(diǎn)進(jìn)行判斷null值，先行節(jié)點(diǎn)為null那么跳出循環(huán)趋箩，此時(shí)后行節(jié)點(diǎn)即為中間節(jié)點(diǎn)赃额。

遞歸從尾到頭輸出單鏈表

• 很簡單，因?yàn)殒湵砩蟻砦覀冎恢李^結(jié)點(diǎn)叫确。而尾遍歷跳芳，尾節(jié)點(diǎn)的特點(diǎn)就是next=NULL。所以我們只需要來個(gè)循環(huán)遞歸的找到遞歸到尾節(jié)點(diǎn)即可竹勉。然后方法棧由里到外依次打印即可飞盆。

 /**
     * 鏈表逆序遞歸遍歷
     *
     * @param headNode
     */
    public static void traverseByRecursive(Node headNode) {
        if (headNode != null) {
            traverseByRecursive(headNode.getNextNode());
            if (headNode.getValue() != HEAD_POINT_NUMBER) {
                System.out.println(headNode.getValue());
            }
        }
    }

反轉(zhuǎn)鏈表

• 遞歸和非遞歸的思想差異。遞歸是從鏈表尾開始兩兩個(gè)體相互反轉(zhuǎn)。而非遞歸實(shí)現(xiàn)是從鏈表頭開始兩兩個(gè)體相互反轉(zhuǎn)吓歇。
• 非遞歸
  • 非遞歸實(shí)現(xiàn)需要注意孽水，每一步我們做了什么。比如4,2,3,3城看。我們第一步拿出了4女气，第二步成了2,4。第三步3,2,4测柠。這樣炼鞠。所以我們應(yīng)該做的是，
    • 首先聲明一個(gè)節(jié)點(diǎn)tempNode轰胁，讓其根據(jù)鏈表循環(huán)向后遍歷鏈表簇搅。直到=null。這樣我們所有元素都反轉(zhuǎn)了软吐。
    • 其次我們發(fā)現(xiàn)第一個(gè)元素抽出的時(shí)候瘩将，即新鏈表的頭我們把他進(jìn)行標(biāo)識firstNode以方便為后續(xù)抽出的節(jié)點(diǎn)的next屬性賦值。比如4凹耙，它的next元素是null而后抽出的元素他們的next元素都是在它前一位抽出的元素姿现。因?yàn)檫@個(gè)next元素的賦值操作發(fā)生在循環(huán)中，且只有一次是null其他幾次都為實(shí)際元素肖抱，所以我們需要聲明一個(gè)節(jié)點(diǎn)nextNode初始化為null备典。當(dāng)他第一次進(jìn)入循環(huán)的時(shí)候，即拿出4的時(shí)候?qū)⑵浞湃雝empNode的next屬性中意述。
    • 然后賦值操作后緊跟著對該nextNode元素進(jìn)行更改提佣，讓其等于新鏈表的頭firstNode。

while (tempNode != null) {
       firstNode = tempNode;
       tempNode = tempNode.getNextNode();
       firstNode.setNextNode(nextNode);
       nextNode = firstNode;
}

• 遞歸

  • 程序分兩種情況處理荤崇，首先做特殊處理拌屏，當(dāng)鏈表只有一個(gè)節(jié)點(diǎn)，或者說該節(jié)點(diǎn)為null的時(shí)候术荤。那么返回該節(jié)點(diǎn)倚喂。
  • 當(dāng)鏈表含有多個(gè)元素的時(shí)候，遞歸依次遍歷該鏈表直到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)(退出條件由第一步控制)瓣戚。最深層遞歸函數(shù)為次深層遞歸函數(shù)返回當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)端圈。
  • 尾元素的next指向他原鏈表的前驅(qū)節(jié)點(diǎn)。前驅(qū)節(jié)點(diǎn)的next指向null子库。
  • 遞歸從最深層返回的頭依次傳遞在遞歸函數(shù)間舱权，從最深層傳到最頂層。供最外層函數(shù)返回仑嗅。

  遞歸需要注意的是：遞歸時(shí)宴倍，每次退出一層遞歸函數(shù)张症，headNode節(jié)點(diǎn)都會前移一位。因?yàn)樽钌顚拥?code>headNode節(jié)點(diǎn)什么都沒做啊楚，只是找到了表尾節(jié)點(diǎn)進(jìn)行返回。

  Node temp;
      if (headNode == null || headNode.getNextNode() == null) {
          temp = headNode;
      } else {
          // A B C- D-
          // temp = D;
          // headNode = C;
          // indexNode = D;
          // A -> B -> C          D -> C -> null
          Node indexNode = recursiveReversalLinklist(headNode.getNextNode());
          headNode.getNextNode().setNextNode(headNode);
          headNode.setNextNode(null);
          temp = indexNode;
      }
      // 反回新鏈表的頭浑彰，遞歸多層函數(shù)間重復(fù)傳遞恭理，
      return temp;
  

單鏈表的擴(kuò)展

• 循環(huán)鏈表
• 雙向鏈表

都很簡單，不贅述了郭变。