一、前言

在上篇文章中，我們詳細的講解了順序表，這里鏈接給大家放在下面，沒看過的同學可以看一看，因為單鏈表就是在順序表之上，做出優化的線性表，

新學期預習嗎？保姆級講解資料結構之順序表的9個方法+手撕代碼

大家還記得順序表中的add方法嗎？那寫起來簡直是一個麻煩，又要考慮pos下標是否合法，還得一個一個的把后面的元素移到前面，這樣一來，不僅代碼寫起來麻煩，代碼執行的時間復雜度也高，但也不是沒有優點，

順序表：由陣列構成，那么它也就包含了陣列的特性，

優點：
1、查詢元素時非常方便快捷，可以通過一個下標，能夠快速的找到當前的資料，O(1).

缺點：
1、每次都會浪費大小不等的記憶體，假設當前陣列大小為20；如果你要放第21個元素的時候，就需要擴容，假設擴容2倍后，大小是40，只放一個元素，那么剩下19個就浪費掉了，
2、每次擴容的時候，都需要拷貝陣列的內容，拷貝的程序中也是需要時間的，造成一定程度資源的浪費，
3、洗掉和插入資料的時候，都需要移動資料，

那么問題來了，有沒有一種表，又不浪費記憶體，洗掉、插入資料的時候還方便快捷呢？

這時候能夠解決上面三個問題的鏈表來了！

二、什么是鏈表？

2.1、鏈表的概念：

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的 ，

2.2、鏈表的分類：鏈表的結構非常多樣化，根據帶頭和不帶頭，雙向和單向，回圈和不回圈可以組成很多種鏈表，

隨便鏈表的種類有很多，但是只需要重點掌握兩種即可，

2.2、兩種重要的單鏈表

1、無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，


1、無頭雙向回圈鏈表：在Java集合框架當中，LinkedList的底層就是由這種鏈表實作的，


注意：每個鏈表的400、200、300均為節點的參考地址，實際上是以16進制的方式存盤的，這里我為了畫圖方便，進行了簡寫，

2.3、關于單鏈表的一些基礎知識

1、鏈表在邏輯上是連續的，但是物理上不一定是連續的，這里的物理上，指的是記憶體地址上，

2、單鏈表的值域：
對于單鏈表來說，每一個節點都3個屬性，在下圖中最上面的123，指的是當前節點的地址(本來應該是16進制，這里為了方便說明用10進制)，val域：val是value的縮寫，就是值的意思，這里存放的是當前節點需要存盤的資訊，
next域：它的型別是一個節點型別，由于單鏈表在邏輯上是連續的，故對于一個節點來說，它不僅需要存放自己的val值，它還需要存放自己的下一個節點的地址->next，以此來實作邏輯上的連續，

3、單鏈表的結構

頭節點+資料節點

三、單鏈表的實作

光說不練假把式，我們了解了鏈表的結構、用處，現在我們來親手實作一個自己的單鏈表，

3.1、窮舉法創建一個簡單的鏈表

這里我先用窮舉的方式一一創建節點，這樣方便理解，下文再講述用其他方法創建鏈表

public class MylinkedList {
    public  ListNode head;//標識這個鏈表的頭
    /**
     * 窮舉法，最簡單的方式把鏈表一個一個列舉出來，
      */
    public  void createList(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(13);
        ListNode listNode3=new ListNode(23);
        ListNode listNode4=new ListNode(33);
        ListNode listNode5=new ListNode(44);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        //head參考 參考的是listNode1參考 參考的物件
        this.head=listNode1;

    }
}
class ListNode{
   public  int val;//值
   public ListNode next;//儲存下一個節點的地址，它是一個參考

    /**
     * 不帶引數的構造方法
     */
    public  ListNode(){

    }
    /**
     * 帶一個引數的構造方法
     */
    public  ListNode(int val){
       this.val=val;
   }
}

現在鏈表有了，那么問題來了，陣列可以通過for回圈的方式遍歷鏈表，或者直接通過陣列下標找到某個節點，那如何遍歷鏈表當中的每個元素呢？

先看這樣一行代碼：

head=head.next;

大家都知道head代表的是頭結點的一個參考，這行代實際上是在修改參考，那把head修改到哪里呢？next指的是當前節點的下一個節點的地址，那么head.next意思就是head的下一個節點，這行代碼就是讓head走到它下一個節點的位置，現在它走到了listNode2的位置，

接下來再看這樣一行代碼

head=head.next.next

聰明如你，假如當前head是listNode2，那么head.next就是listNode3的地址就指的是234，它后面再加一個next，就再指向在一個地址就是了，所以它的意思是讓從listNode2走到listNode4的位置，

慢慢的我們發現，我們可以通過head=head.next的方式讓head這個參考不停的指向下一個節點，這難道不就是在遍歷鏈表嗎？我們讓head走頭開始，每走過一個節點，列印一個節點對應的val值，直到走到最后一個節點，

接下來我們來實作這個方法，

3.2、遍歷鏈表

上面我們已經知道了遍歷鏈表的方式是讓head一直等于head.next，我們如果需要遍歷整個鏈表，就需要給他加一個限制條件，考慮到head具有特殊的含義，我們這里用一個cur節點來遍歷鏈表，this.head=!null

 /**
     *遍歷鏈表
     *
     */
    public  void disPlay(){
        ListNode cur=this.head;
       while (cur!=null){
           /**
            * 注意不能while回圈的判斷條件不能寫成
            * this.head.next!=null，
            * 這樣的話，最后一個節點是不能被列印的
            *
            */
           System.out.println(this.head.val);
           cur=cur.next;
       }
          System.out.println();
    }

總結：如果想遍歷完鏈表，一定得是cur！==null，這樣才算是遍歷完了，

有了上面的基礎，接下來我們在實作一些更復雜的方法，

3.3、得到鏈表的長度

思路是遍歷一遍鏈表，定義一個計數器count，每遍歷一個節點就讓count+1,遍歷完成后，回傳count的值就是鏈表的長度了，

上代碼！

 //得到單鏈表的長度
    public int size(){
        int count=0;
        ListNode cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

size方法和display方法差別在多了一個計數器，在同樣遍歷遍歷的基礎下，display方法是列印鏈表的val值，而size方法是讓計數器count+1.

3.4、頭插法

1、剛剛我們以窮舉法這樣的方式創建了一個鏈表，現在我們用頭插法創建鏈表，

對于兩種鏈表，兩種不同的頭插法方式，

（1）：對于無頭單向鏈表，

用藍色字體的Node節點是需要頭插的節點，它當前的val值是110，地址是777，next域是null，對于沒有頭結點的鏈表，頭插法就是直接把需要插入的節點放到當前鏈表的第一個位置即可，

如圖：

對于單向有頭鏈表頭插法就需要把插入的元素放到head節點和head下一個節點直接，因為有頭的鏈表，head不能變，

如圖：

上代碼！

   //頭插法   無頭單向鏈表
    public void addFirst(int data){
   ListNode Node=new ListNode(data);
   Node.next=this.head;
   this.head=Node;
    }

3.5、尾插法

尾插法顧名思義，和頭插法相似，尾插法把需要插入的節點插入到鏈表的尾部即可，但是問題來了，頭插法可以直接插是因為鏈表本來就有head節點，但是鏈表并沒有特別指出尾巴在哪里，所為尾插法第一個要做的是就是找到鏈表的尾巴，然后在插入到最后，修改next，

1、找尾巴：找尾巴還是和size方法類似，定義一個cur節點，讓他一直遍歷，直到cur.next==null，就找到尾巴了，這時停止回圈，不然就指向下一個節點，

2、修改next：找到尾巴之后，讓cur.next=Node就好，讓鏈表原本的尾巴，指向現在的Node節點，

3、還有一件事：萬一鏈表是空的呢？那就是第一次插入了，這時直接讓head=node就好，

上代碼！

   //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        //第一次和不是第一次
        if(this.head==null){
            this.head=node;
        }
        else {
            ListNode cur=this.head;
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }

3.6、 任意位置插入節點

這個方法的意思就是在某一個位置，插入一個節點，第一個資料節點為0號下標，以此類推，

這時，需要修改的域有，上一個節點的next域，因為插入后它的next域就應當是當前插入節點的地址了，還有就是當前節點的next域，把它的next域修改成原本3號下標節點的地址，以下是插入的步驟和特殊情況處理，

我們先相處一個基礎版的代碼：

node.next=cur.next;
cur.next=node;

0、index位置小于0或者比鏈表長度還大怎么辦？

1、需要找到插入位置的前一個節點的地址，在上圖是需要先找到1號下標節點的地址，

2、0位置可沒有前一個節點，

3、要插入到最后一個節點怎么做？

這些問題，都會在代碼中解決，

4、找到index下標前一個節點的方法 findInddexSubOne
讓一個參考從頭開始，走index-1步，這是這個參考指向的就是前一個節點，

   /**
     * 讓一個參考從頭開始，走index-1步
     * @param index
     * @return
     */
    public  ListNode findInddexSubOne(int index){
       int count=0;
       ListNode cur=this.head;
       while (count!=index-1){
           cur=cur.next;
           count++;
       }
       return  cur;

    }

整個方法代碼如下：
它有點長，你忍一下，

    //任意位置插入,第一個資料節點為0號下標
    public void  addIndex(int index,int data){
        //1、判斷index是否合法
        if(index<0 ||index >size()){
            System.out.println("index位置不合法");
            return;
        }
        //2、index為0，直接頭插法
           if(index==0){
               addFirst(data);
               return;
           }

        //3、index==size()，直接尾插法
           if(index==size()){
               addLast(data);
               return;
           }

        /**
         * 4、正常的情況
         *  cur指向的是一個index-1位置的節點
         */
        ListNode cur=findInddexSubOne(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;


    }

    /**
     * 讓一個參考從頭開始，走index-1步
     * @param index
     * @return
     */
    public  ListNode findInddexSubOne(int index){
       int count=0;
       ListNode cur=this.head;
       while (count!=index-1){
           cur=cur.next;
           count++;
       }
       return  cur;

    }

3.7、查找是否包含關鍵字key是否在單鏈表當中

遍歷鏈表，定義一個cur參考，從鏈表的頭開始，如果cur的val值和key相等了，就回傳true，如果遍歷完了，還沒有找到，那就是沒有，回傳false，

方法代碼如下：

    //查找是否包含關鍵字key是否在單鏈表當中
    public boolean contains(int key){
        ListNode cur=this.head;
        while (cur!=null){
            if(cur.val==key){
              return  true;
            }
        }
        
return  false;
    }

3.8、洗掉所有節點

由于鏈表是都 next域一個個連接起來的，那么洗掉所以節點的一個粗暴的方法就是把所有的next置空，讓每個節點都找不到下一個節點，這樣鏈表就連接不起來，就算是洗掉了，

第一次嘗試：我們試試是否可以像之前遍歷鏈表一樣，將每次經過的cur節點置空它的next域，這樣就把整個鏈表刪完了，

但是當我們實際操作的時候發現，當你將cur節點的next域洗掉的時候，那它要怎么找到下一個節點呢？

我們在定義一個節點curNext保存cur下一個節點就是了，這樣每次洗掉的時候，curNext還可以指向下一個節點，洗掉完之后再讓cur指向curNext，

還有一件事！
節點還有頭結點沒有洗掉，所以當回圈走完，我們還需要讓head節點置空，這樣就是真正的把所有節點洗掉了，

上代碼！

  //洗掉所有節點
    public void clear(){
        ListNode cur=this.head;
        while (cur!=null){
            ListNode curNext=cur.next;
            cur.next=null;
            cur=curNext;
        }
        this.head=null;
    }

3.9、洗掉第一次出現關鍵字為key的節點

假設要洗掉的節點是6，下標為del，我們只需要找到它的前驅節點prev，直接讓這個前驅節點和del的下一個節點相連，就變向的忽略的del節點，這就算是洗掉這個這點了，

總結：
1、找到待洗掉節點的前驅節點和下一個節點
2、將前驅節點的next域指向待洗掉節點的next域，
3、有一種特殊情況是頭結點是需要洗掉的節點，那么直接置空就好，

具體細節都在代碼中，找到前驅節點我寫成了一個方法search在下面的代碼中

    //找到前序節點 服務于  洗掉第一次出現關鍵字為key的節點
    public  ListNode searchPrev(int key){
        ListNode prev=this.head;
        while (prev!=null){
            if(prev.next.val==key){
                return  prev;
            }
            prev=prev.next;
        }
        return  null; //找完了都沒回傳，說明沒有找到這個節點，
    }

洗掉方法

 //洗掉第一次出現關鍵字為key的節點
    public void remove(int key){
    //0、頭結點是要洗掉的節點

        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
    //1、找到要洗掉節點的前驅節點
    ListNode prev=searchPrev(key);
        if(prev==null){
            System.out.println("沒有你要洗掉的節點");
            return;

        }
    //2、開始洗掉節點
      ListNode del=prev.next;
        prev.next=del.next;
    }

3.10、洗掉所有值為key的節點

1、上面我們已經寫了9個方法了，相信大家單鏈表已經掌握的不錯了，這是最后一個方法，我們這次將難度上升到面試的高度！ 在只遍歷鏈表一遍的情況下，洗掉所有值為key的節點，

如下圖，有兩個val值為45的節點，我們這個方法需要只遍歷鏈表一遍，就洗掉這兩個val值為45的節點，

思路：
1.定義cur為當前要洗掉的節點，prev為洗掉節點的前驅節點，每次判斷cur.val是否等于key，如果等于key就把prev.next指向cur.next，如果不相等，就讓cur和prev一起向后走，

上代碼

  //洗掉所有值為key的節點
    public void removeAllKey(int key){
       ListNode prev=this.head;
       ListNode cur=this.head.next;
       while (cur!=null){
           if(cur.val==key){
               prev.next=cur.next;
               cur=cur.next;
           }
           else {
               prev=cur;
               cur=cur.next;
           }
       }
       //別忘了頭結點
       if(this.head.val==key){
           this.head=this.head.next;
       }
    }

只遍歷一遍就完成了洗掉所以val值等于key的節點，你真棒!

四、LeetCode和劍指Offer上的單鏈表面試題

上面學習完了，怎么創建一個自己單鏈表，并且完成了單鏈表的10個方法，現在來試試挑戰面試題把，題解在下方，加油哦！

劍指 Offer II 021. 洗掉鏈表的倒數第 n 個結點

LeetCode 24：兩兩交換鏈表中的節點、1662. 檢查兩個字串陣列是否相等

leetcode 21. 合并兩個有序鏈表

五、其他練習題

我還總結了一些LeetCode和劍指offer的題解，一起來看看吧！，

劍指 Offer 67. 把字串轉換成整數

怎么把i am a student逆置成student a am i？面試題逆置字串講解

三種方法任君挑選 LeetCode_136只出現一次的數字

什么？動態規劃10行求出連續子陣列的最大和 劍指offer-42講解

劍指 Offer 39. 陣列中出現次數超過一半的數字 簡單易懂14行搞定 ，人人皆可會

二叉樹的層序遍歷原理+LeetCode真題練習

劍指 Offer 58 - II. 左旋轉字串的三種解法一起看看吧！！

字串“aabcccccaaa”壓縮成“a2b1c5a3“還要回傳更小的？力扣面試題 01.06. 字串壓縮講解

字串bit666keji123“中數字的個數？

找到不重復的數字進階版 空間復雜度O(1),時間O(n)平方，不能修改陣列內容，不能對陣列進行排序

LeetCode_231. 判斷一個數是否為2 的冪，與運算一行代碼解決

驗證尼科徹斯定理，即：任何一個整數m的立方都可以寫成m個連續奇數之和