1.什么是鏈表

鏈表是一種通過指標串聯在一起的線性結構，每一個節點由兩部分組成，一個是資料域一個是指標域（存放指向下一個節點的指標），最后一個節點的指標域指向null（空指標的意思），鏈接的入口節點稱為鏈表的頭結點也就是head，

2.鏈表的型別

2.1單鏈表

見上圖

2.2雙鏈表

單鏈表中的指標域只能指向節點的下一個節點，雙鏈表：每一個節點有兩個指標域，一個指向下一個節點，一個指向上一個節點，雙鏈表既可以向前查詢也可以向后查詢，

2.3回圈鏈表

回圈鏈表，顧名思義，就是鏈表首尾相連，回圈鏈表可以用來解決約瑟夫環問題，

3.鏈表存盤方式

陣列是在記憶體中是連續分布的，但是鏈表在記憶體中可不是連續分布的，鏈表是通過指標域的指標鏈接在記憶體中各個節點，所以鏈表中的節點在記憶體中不是連續分布的，而是散亂分布在記憶體中的某地址上，分配機制取決于作業系統的記憶體管理，

4.鏈表的定義（需要關注）

鏈表節點的定義，很多同學在面試的時候都寫不好，這是因為平時在刷leetcode的時候，鏈表的節點都默認定義好了，直接用就行了，所以同學們都沒有注意到鏈表的節點是如何定義的，而在面試的時候，一旦要自己手寫鏈表，就寫的錯漏百出，

// 單鏈表
struct ListNode {
    int val;  // 節點上存盤的元素
    ListNode *next;  // 指向下一個節點的指標
    ListNode(int x) : val(x), next(NULL) {}  // 節點的建構式
};

java定義如下：

public class ListNode {
    // 結點的值
    int val;
    // 下一個結點
    ListNode next;
    // 節點的建構式(無參)
    public ListNode() {
    }

    // 節點的建構式(有一個引數)
    public ListNode(int val) {
        this.val = val;
    }

    // 節點的建構式(有兩個引數)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}