線性表

定義：線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)拜姿。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。其實(shí)除了數(shù)組冯遂，鏈表蕊肥、隊(duì)列、棧等也是線性表結(jié)構(gòu)蛤肌。

線性表

數(shù)組

定義：數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)壁却。它用一組連續(xù)的內(nèi)存空間，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)裸准。

特性

**數(shù)組支持隨機(jī)訪問展东，根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為 O(1)*

a[i]_address = base_address + i * data_type_size

插入

1. 如果數(shù)組有序，如果要將某個(gè)數(shù)據(jù)插入到第 k 個(gè)位置炒俱，則插入操作需要多次的數(shù)據(jù)搬移工作來清空該位置盐肃，為插入操作進(jìn)行準(zhǔn)備，這時(shí)候的平均時(shí)間復(fù)雜度O(n) = (1+2+3+...+n)/n = O(n)
2. 如果數(shù)組無序权悟，如果要將某個(gè)數(shù)據(jù)插入到第 k 個(gè)位置砸王，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個(gè)位置峦阁，這時(shí)候平均時(shí)間復(fù)雜度就會(huì)變成O(1)

刪除

1. 與插入類似谦铃，如果刪除末尾元素，這時(shí)候時(shí)間復(fù)雜度為O(1);如果刪除第一個(gè)元素拇派，時(shí)間復(fù)雜度O(n),刪除任意位置的平均時(shí)間復(fù)雜度 = O(n);

2. 在某些特殊場(chǎng)景下荷辕，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性。如果我們將多次刪除操作集中在一起執(zhí)行件豌，刪除的效率會(huì)提高很多疮方，如JVM的標(biāo)記清除算法的核心思想

   case：數(shù)組 a[10]中存儲(chǔ)了 8 個(gè)元素：a，b茧彤，c骡显，d，e，f惫谤，g壁顶，h。現(xiàn)在溜歪，我們要依次刪除 a若专，b，c 三個(gè)元素蝴猪。

   
   

   數(shù)據(jù)批量刪除操作

   為了避免 d调衰，e，f自阱，g嚎莉，h 這幾個(gè)數(shù)據(jù)會(huì)被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)沛豌。每次的刪除操作并不是真正地搬移數(shù)據(jù)趋箩，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲(chǔ)數(shù)據(jù)時(shí)加派，我們?cè)儆|發(fā)執(zhí)行一次真正的刪除操作叫确，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

查詢

• 根據(jù)數(shù)組下標(biāo)進(jìn)行查詢芍锦，平均時(shí)間復(fù)雜度 = O(1);
• 根據(jù)數(shù)組元素進(jìn)行查詢, 因?yàn)樯婕暗綌?shù)組元素的比較启妹，所以平均時(shí)間復(fù)雜度 = O(n);

注意事項(xiàng)：

• 警惕數(shù)組下標(biāo)越界問題

• ArrayList為防止因擴(kuò)容操作造成的數(shù)據(jù)搬移需要注意以下3點(diǎn)：

  1. 能不使用就不要使用默認(rèn)構(gòu)造函數(shù)；
  2. 當(dāng)知道列表容量的時(shí)候醉旦，最好用指定的容量來創(chuàng)建實(shí)例饶米；
  3. 不知道列表容量，預(yù)估一個(gè)稍微大于容量的值來創(chuàng)建實(shí)例车胡；

• 容器ArrayList和數(shù)據(jù)Array比較

  1. Java ArrayList 無法存儲(chǔ)基本類型檬输，比如 int、long匈棘，需要封裝為 Integer丧慈、Long 類，而 Autoboxing主卫、Unboxing 則有一定的性能消耗逃默，所以如果特別關(guān)注性能，或者希望使用基本類型簇搅，就可以選用數(shù)組完域。
  2. 如果數(shù)據(jù)大小事先已知，并且對(duì)數(shù)據(jù)的操作非常簡(jiǎn)單瘩将，用不到 ArrayList 提供的大部分方法吟税，也可以直接使用數(shù)組凹耙。
  3. 當(dāng)要表示多維數(shù)組時(shí)，用數(shù)組往往會(huì)更加直觀肠仪。比如 Object[][][][] array肖抱；而用容器的話則需要這樣定義：ArrayList <ArrayList<Object>> arrayList。

小結(jié)：

1. 對(duì)于業(yè)務(wù)開發(fā)异旧，直接使用容器就足夠了意述，省時(shí)省力。畢竟損耗一丟丟性能吮蛹，完全不會(huì)影響到系統(tǒng)整體的性能欲险。但如果你是做一些非常底層的開發(fā)，比如開發(fā)網(wǎng)絡(luò)框架匹涮，性能的優(yōu)化需要做到極致，這個(gè)時(shí)候數(shù)組就會(huì)優(yōu)于容器槐壳，成為首選然低。

數(shù)組相關(guān)case

1.0-n-1缺失的數(shù)

2.在排序數(shù)組中查找數(shù)字

3.盛水最多的容器

鏈表

單鏈表

定義：

鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起。其中务唐，我們把內(nèi)存塊稱為鏈表的“**結(jié)點(diǎn)**”雳攘。為了將所有的結(jié)點(diǎn)串起來，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外枫笛，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)的地址吨灭。如圖所示，我們把這個(gè)記錄下個(gè)結(jié)點(diǎn)地址的指針叫作**后繼指針 next**刑巧。

單鏈表

其中有兩個(gè)結(jié)點(diǎn)是比較特殊的喧兄，它們分別是第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。我們習(xí)慣性地把第一個(gè)結(jié)點(diǎn)叫作頭結(jié)點(diǎn)啊楚，把最后一個(gè)結(jié)點(diǎn)叫作尾結(jié)點(diǎn)吠冤。其中，頭結(jié)點(diǎn)用來記錄鏈表的基地址恭理。有了它拯辙，我們就可以遍歷得到整條鏈表。而尾結(jié)點(diǎn)特殊的地方是：指針不是指向下一個(gè)結(jié)點(diǎn)颜价，而是指向一個(gè)空地址 NULL涯保，表示這是鏈表上最后一個(gè)結(jié)點(diǎn)。

插入周伦、刪除

與數(shù)組插入夕春、刪除相比，鏈表的相關(guān)操作不涉及的數(shù)據(jù)的搬移操作专挪，僅是**改變相鄰節(jié)點(diǎn)指針的改變**撇他，所以對(duì)于的時(shí)間復(fù)雜度 = **O(1)**;

鏈表的插入刪除操作

查詢

由于鏈表地址不連續(xù)茄猫，無法根據(jù)首地址和下標(biāo)，通過尋址公式就能直接計(jì)算出對(duì)應(yīng)的內(nèi)存地址困肩，而是需要根據(jù)指針一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)地**依次遍歷**划纽，直到找到相應(yīng)的結(jié)點(diǎn)，這時(shí)候隨機(jī)訪問的時(shí)間復(fù)雜度 = **O(n)**锌畸。

循環(huán)鏈表

定義

循環(huán)鏈表是一種特殊的單鏈表勇劣。實(shí)際上，循環(huán)鏈表也很簡(jiǎn)單潭枣。它跟單鏈表唯一的區(qū)別就在尾結(jié)點(diǎn)比默。我們知道，單鏈表的尾結(jié)點(diǎn)指針指向空地址盆犁，表示這就是最后的結(jié)點(diǎn)了命咐。而循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)。

循環(huán)鏈表

特性：

單鏈表相比谐岁，循環(huán)鏈表的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便醋奠。當(dāng)要處理的**數(shù)據(jù)具有環(huán)型結(jié)構(gòu)**特點(diǎn)時(shí)，就特別適合采用**循環(huán)鏈表**伊佃。比如著名的**約瑟夫問題**窜司。

雙向鏈表

定義

單向鏈表只有一個(gè)方向，結(jié)點(diǎn)只有一個(gè)后繼指針 next 指向后面的結(jié)點(diǎn)航揉。而雙向鏈表塞祈，顧名思義，它支持兩個(gè)方向帅涂，每個(gè)結(jié)點(diǎn)不止有一個(gè)后繼指針 next 指向后面的結(jié)點(diǎn)议薪，還有一個(gè)前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)。

雙向鏈表

特性

雙向鏈表可以支持 **O(1) 時(shí)間復(fù)雜度的情況下找到前驅(qū)結(jié)點(diǎn)**媳友，正是這樣的特點(diǎn)笙蒙，也使雙向鏈表在某些情況下的插入、刪除等操作都要比單鏈表簡(jiǎn)單庆锦、高效捅位。

在實(shí)際的軟件開發(fā)中，從鏈表中刪除一個(gè)數(shù)據(jù)無外乎這兩種情況：

1. 刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)搂抒；
2. 刪除給定指針指向的結(jié)點(diǎn)艇搀。

對(duì)于第一種情況，不管是單鏈表還是雙向鏈表求晶，為了查找到值等于給定值的結(jié)點(diǎn)焰雕，都需要從頭結(jié)點(diǎn)開始一個(gè)一個(gè)依次遍歷對(duì)比，直到找到值等于給定值的結(jié)點(diǎn)芳杏，然后再通過我前面講的指針操作將其刪除矩屁。

盡管單純的刪除操作時(shí)間復(fù)雜度是 O(1)辟宗，但遍歷查找的時(shí)間是主要的耗時(shí)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為 O(n)吝秕。根據(jù)時(shí)間復(fù)雜度分析中的加法法則泊脐，刪除值等于給定值的結(jié)點(diǎn)對(duì)應(yīng)的鏈表操作的總時(shí)間復(fù)雜度為 O(n)。

對(duì)于第二種情況烁峭，我們已經(jīng)找到了要?jiǎng)h除的結(jié)點(diǎn)容客，但是刪除某個(gè)結(jié)點(diǎn) q 需要知道其前驅(qū)結(jié)點(diǎn)，而單鏈表并不支持直接獲取前驅(qū)結(jié)點(diǎn)约郁，所以缩挑，為了找到前驅(qū)結(jié)點(diǎn)，我們還是要從頭結(jié)點(diǎn)開始遍歷鏈表鬓梅，直到 p->next=q供置，說明 p 是 q 的前驅(qū)結(jié)點(diǎn)。

但是對(duì)于雙向鏈表來說绽快，這種情況就比較有優(yōu)勢(shì)了芥丧。因?yàn)?strong>雙向鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針，不需要像單鏈表那樣遍歷谎僻。所以，針對(duì)第二種情況寓辱，單鏈表刪除操作需要 O(n) 的時(shí)間復(fù)雜度艘绍，而雙向鏈表只需要在 O(1) 的時(shí)間復(fù)雜度內(nèi)就搞定了！

同理秫筏，如果我們希望在鏈表的某個(gè)指定結(jié)點(diǎn)前面插入一個(gè)結(jié)點(diǎn)，雙向鏈表比單鏈表有很大的優(yōu)勢(shì)航夺。雙向鏈表可以在 O(1) 時(shí)間復(fù)雜度搞定崔涂，而單向鏈表需要 O(n) 的時(shí)間復(fù)雜度阳掐。

除了插入缭保、刪除操作有優(yōu)勢(shì)之外，對(duì)于一個(gè)有序鏈表蝙茶，雙向鏈表的按值查詢的效率也要比單鏈表高一些。因?yàn)槲覀兛梢杂涗浬洗尾檎业奈恢?p钳恕，每次查詢時(shí)忧额，根據(jù)要查找的值與 p 的大小關(guān)系，決定是往前還是往后查找轴脐，所以平均只需要查找一半的數(shù)據(jù)大咱。

現(xiàn)在碴巾，你有沒有覺得雙向鏈表要比單鏈表更加高效呢厦瓢？這就是為什么在實(shí)際的軟件開發(fā)中煮仇，雙向鏈表盡管比較費(fèi)內(nèi)存浙垫，但還是比單鏈表的應(yīng)用更加廣泛的原因夹姥。如果你熟悉 Java 語言辙诞，你肯定用過 LinkedHashMap 這個(gè)容器旦部。如果你深入研究 LinkedHashMap 的實(shí)現(xiàn)原理较店，就會(huì)發(fā)現(xiàn)其中就用到了雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)泽西。

實(shí)際上捧杉，這里有一個(gè)更加重要的知識(shí)點(diǎn)需要你掌握，那就是用空間換時(shí)間的設(shè)計(jì)思想灰粮。當(dāng)內(nèi)存空間充足的時(shí)候粘舟，如果我們更加追求代碼的執(zhí)行速度柑肴，我們就可以選擇空間復(fù)雜度相對(duì)較高晰骑、但時(shí)間復(fù)雜度相對(duì)很低的算法或者數(shù)據(jù)結(jié)構(gòu)硕舆。相反，如果內(nèi)存比較緊缺凌节，比如代碼跑在手機(jī)或者單片機(jī)上刊咳，這個(gè)時(shí)候，就要反過用時(shí)間換空間的設(shè)計(jì)思路捕犬。

雙向循環(huán)鏈表

雙向循環(huán)鏈表

數(shù)組鏈表比較

數(shù)據(jù)與鏈表比較

鏈表相關(guān)case

鏈表編寫的注意事項(xiàng)：

1. 理解指針或引用的含義

   指針或引用：都是存儲(chǔ)所指對(duì)象的內(nèi)存地址

   將某個(gè)變量賦值給指針，實(shí)際上就是將這個(gè)變量的地址賦值給指針垢粮，或者反過來說蜡吧，指針中存儲(chǔ)了這個(gè)變量的內(nèi)存地址昔善，指向了這個(gè)變量君仆，通過指針就能找到這個(gè)變量返咱。

   p->next=q洛姑。//這行代碼是說楞艾，p 結(jié)點(diǎn)中的 next 指針存儲(chǔ)了 q 結(jié)點(diǎn)的內(nèi)存地址硫眯。
   p->next=p->next->next两入。//這行代碼表示裹纳，p 結(jié)點(diǎn)的 next 指針存儲(chǔ)了 p 結(jié)點(diǎn)的下下一個(gè)結(jié)點(diǎn)的內(nèi)存地址敏储。
   

2. 警惕指針丟失和內(nèi)存泄漏

   • 插入結(jié)點(diǎn)時(shí)已添，一定要注意操作的順序更舞，要先將結(jié)點(diǎn) x 的 next 指針指向結(jié)點(diǎn) b缆蝉，再把結(jié)點(diǎn) a 的 next 指針指向結(jié)點(diǎn) x刊头，這樣才不會(huì)丟失指針芽偏，導(dǎo)致內(nèi)存泄漏污尉。
   插入節(jié)點(diǎn)
   • 刪除鏈表結(jié)點(diǎn)時(shí)某宪，也一定要記得手動(dòng)釋放內(nèi)存空間

3. 利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度

   • 針對(duì)鏈表的插入兴喂、刪除操作衣迷，需要對(duì)插入第一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)的情況進(jìn)行特殊處理壶谒。如果我們引入哨兵結(jié)點(diǎn)，在任何時(shí)候陨界，不管鏈表是不是空菌瘪，head 指針都會(huì)一直指向這個(gè)哨兵結(jié)點(diǎn)麻车。我們也把這種有哨兵結(jié)點(diǎn)的鏈表叫帶頭鏈表。相反表箭，沒有哨兵結(jié)點(diǎn)的鏈表就叫作不帶頭鏈表免钻。

     //插入操作
     new_node->next = p->next;
     p->next = new_node;
     
     //頭部插入
     if (head == null) {
       head = new_node;
     }
     //刪除操作
     p->next = p->next->next;
     //尾結(jié)點(diǎn)刪除
     if (head->next == null) {
        head = null;
     }
     
     //不帶頭鏈表操作
     
     // 在數(shù)組a中凤覆，查找key盯桦，返回key所在的位置
     // 其中拥峦，n表示數(shù)組a的長(zhǎng)度
     int find(char* a, int n, char key) {
       // 邊界條件處理略号，如果a為空玄柠，或者n<=0，說明數(shù)組中沒有數(shù)據(jù)铐伴，就不用while循環(huán)比較了
       if(a == null || n <= 0) {
         return -1;
       }
     
       int i = 0;
       // 這里有兩個(gè)比較操作：i<n和a[i]==key.
       while (i < n) {
         if (a[i] == key) {
           return i;
         }
         ++i;
       }
     
       return -1;
     }
     
     //帶頭鏈表操作
     
     // 在數(shù)組a中当宴，查找key户矢，返回key所在的位置
     // 其中，n表示數(shù)組a的長(zhǎng)度
     // 我舉2個(gè)例子挂洛，你可以拿例子走一下代碼
     // a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
     // a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
     int find(char* a, int n, char key) {
       if(a == null || n <= 0) {
         return -1;
       }
     
       // 這里因?yàn)橐獙[n-1]的值替換成key虏劲，所以要特殊處理這個(gè)值
       if (a[n-1] == key) {
         return n-1;
       }
     
       // 把a(bǔ)[n-1]的值臨時(shí)保存在變量tmp中励堡，以便之后恢復(fù)应结。tmp=6摊趾。
       // 之所以這樣做的目的是：希望find()代碼不要改變a數(shù)組中的內(nèi)容
       char tmp = a[n-1];
       // 把key的值放到a[n-1]中砾层，此時(shí)a = {4, 2, 3, 5, 9, 7}
       a[n-1] = key;
     
       int i = 0;
       // while 循環(huán)比起代碼一，少了i<n這個(gè)比較操作
       while (a[i] != key) {
         ++i;
       }
     
       // 恢復(fù)a[n-1]原來的值,此時(shí)a= {4, 2, 3, 5, 9, 6}
       a[n-1] = tmp;
     
       if (i == n-1) {
         // 如果i == n-1說明侨糟，在0...n-2之間都沒有key秕重，所以返回-1
         return -1;
       } else {
         // 否則溶耘，返回i，就是等于key值的元素的下標(biāo)
         return i;
       }
     }
     

     帶頭鏈表

4. 重點(diǎn)留意邊界條件處理

   • 如果鏈表為空時(shí)庐扫，代碼是否能正常工作？
   • 如果鏈表只包含一個(gè)結(jié)點(diǎn)時(shí)萨醒，代碼是否能正常工作验靡？
   • 如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)胜嗓，代碼是否能正常工作？
   • 代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候变过，是否能正常工作媚狰？

5. 舉例畫圖崭孤，輔助思考 -- 舉例法和畫圖法。

   鏈表--舉例法和畫圖法

6. 多寫多練嗤形，沒有捷徑

   • 單鏈表反轉(zhuǎn)
     • 翻轉(zhuǎn)鏈表（使用遞歸，迭代兩種方法）
   • 鏈表中環(huán)的檢測(cè)
     • 求單鏈表是否有環(huán)
   • 兩個(gè)有序的鏈表合并
     • 合并兩個(gè)有序鏈表
   • 刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
   • 求鏈表的中間結(jié)點(diǎn)
   • 判斷鏈表是否相交
   • 求鏈表相交的起點(diǎn)

最近最少使用策略 LRU

緩存淘汰策略來決定毡惜。常見的策略有三種：先進(jìn)先出策略 FIFO（First In，F(xiàn)irst Out）帕膜、最少使用策略 LFU（Least Frequently Used）垮刹、最近最少使用策略 LRU（Least Recently Used）酪劫。

問題：

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)覆糟，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制 滩字。
實(shí)現(xiàn) LRUCache 類：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值挟裂，否則返回 -1 话瞧。
void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值埃篓；如果關(guān)鍵字不存在架专，則插入該組「關(guān)鍵字-值」部脚。當(dāng)緩存容量達(dá)到上限時(shí)委刘，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間淆珊。

進(jìn)階：你是否可以在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作往声？

示例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會(huì)使得關(guān)鍵字 2 作廢浩销，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會(huì)使得關(guān)鍵字 1 作廢柬采，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多調(diào)用 3 * 104 次 get 和 put

思路：我們維護(hù)一個(gè)有序單鏈表礁遣，越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪問的祟霍。當(dāng)有一個(gè)新的數(shù)據(jù)被訪問時(shí)，我們從鏈表頭開始順序遍歷鏈表崭添。

1. 如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個(gè)數(shù)據(jù)對(duì)應(yīng)的結(jié)點(diǎn)屁置，并將其從原來的位置刪除蓝角，然后再插入到鏈表的頭部。

2. 如果此數(shù)據(jù)沒有在緩存鏈表中并徘，又可以分為兩種情況：

   • 如果此時(shí)緩存未滿蕴茴，則將此結(jié)點(diǎn)直接插入到鏈表的頭部倦淀；

   • 如果此時(shí)緩存已滿，則鏈表尾結(jié)點(diǎn)刪除插龄，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部愿棋。

優(yōu)化：思路2：引入散列表（Hash Table）來記錄每個(gè)數(shù)據(jù)的位置，將緩存訪問的時(shí)間復(fù)雜度降到 O(1)均牢，同時(shí)使用雙向鏈表來獲取前一個(gè)節(jié)點(diǎn)

class LRUCache {
    private class CacheNode{
        private int key;
        private int value;
        private CacheNode prev;
        private CacheNode next;

        public CacheNode(int key,int value){
            this.key = key;
            this.value =value;
            this.prev = null;
            this.next = null; 
        }
    }
    private int capacity;
    // 在時(shí)間復(fù)雜度O(1)的情況下找到節(jié)點(diǎn)
    private Map<Integer,CacheNode> cacheNodeMap = new HashMap<Integer,CacheNode>();

    //哨兵節(jié)點(diǎn)-頭節(jié)點(diǎn)
    private CacheNode head = new CacheNode(-1,-1);
    //哨兵節(jié)點(diǎn)-尾節(jié)點(diǎn)
    private CacheNode tail = new CacheNode(-1,-1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head.next = tail;
        this.tail.prev = head;
    }
    
    public int get(int key) {
        //不存在糠雨，返回-1
        if(!cacheNodeMap.containsKey(key)){
            return -1;
        }
        // 如果存在，則將該節(jié)點(diǎn)移動(dòng)到頭部徘跪，并返回
        CacheNode node = cacheNodeMap.get(key);

        node.prev.next = node.next;
        node.next.prev = node.prev;
        moveToHead(node);

        return cacheNodeMap.get(key).value;
    }
    
    public void put(int key, int value) {

        if(this.get(key) != -1){
            // 查詢到緩存中存在key相同的節(jié)點(diǎn)，這時(shí)需要將原節(jié)點(diǎn)替換為新節(jié)點(diǎn)垮庐，并更新cacheNodeMap
            if(this.cacheNodeMap.get(key).value != value){
                CacheNode node  = this.cacheNodeMap.get(key);
                node.prev.next = node.next;
                node.next.prev = node.prev;
                node = new CacheNode(key,value);
                moveToHead(node);
                cacheNodeMap.put(key, node);

            }
        }else{
            // 未找到松邪，判斷緩存是否已滿
            if(cacheNodeMap.size() >= capacity){
                // 如果已滿，則刪除尾部節(jié)點(diǎn)再插入的頭部
                //刪除尾結(jié)點(diǎn)
                cacheNodeMap.remove(tail.prev.key);
                CacheNode prevNode = tail.prev.prev;
                tail.prev = prevNode;
                prevNode.next = tail;
            }
                //插入的頭部
                CacheNode node = new CacheNode(key,value);
                moveToHead(node);
                cacheNodeMap.put(key, node);
        }
            

    }

    private void moveToHead(CacheNode node){
        node.next =head.next;
        head.next = node;
        node.prev = head;
        node.next.prev = node;
    }
}

鏈表翻轉(zhuǎn)

題目1鏈接：https://leetcode-cn.com/problems/reverse-linked-list/

反轉(zhuǎn)一個(gè)單鏈表哨查。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表逗抑。你能否用兩種方法解決這道題？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
      /**
           * 思路：首先設(shè)置三個(gè)節(jié)點(diǎn)：
           *  prev 前驅(qū)節(jié)點(diǎn) --記錄翻轉(zhuǎn)后的指向位置
           *  current 當(dāng)前節(jié)點(diǎn)
           *  next 后驅(qū)節(jié)點(diǎn) -- 用于記錄翻轉(zhuǎn)前的指向位置
           * 流程：首先判斷是否為空鏈表 head == null解恰，如果為空鏈表則結(jié)束锋八；
           *      如果不為空，首先prev前驅(qū)節(jié)點(diǎn)指向 null 护盈，然后current 指向prev節(jié)點(diǎn)挟纱，整體向后移動(dòng)一位，循環(huán)遍歷直到全部遍歷完成
           *      (current == null)結(jié)束返回翻轉(zhuǎn)后的頭結(jié)點(diǎn)prev腐宋。
           * 邊界條件： 0個(gè)節(jié)點(diǎn)紊服；1個(gè)節(jié)點(diǎn)；2個(gè)節(jié)點(diǎn)
           *
           */
        if(head == null) return head;

        ListNode prev = head;
        ListNode current  = prev.next;
        prev.next = null;
        while(current != null){
            ListNode next = current.next;
            current.next = prev;

            prev = current;
            current = next;
        }

        return prev;

    }
}

題目2 鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii/

反轉(zhuǎn)從位置 m 到 n 的鏈表胸竞。請(qǐng)使用一趟掃描完成反轉(zhuǎn)欺嗤。

說明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

  
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
 /**
  *思路：為了保證head節(jié)點(diǎn)位置移動(dòng)的影響卫枝，這里設(shè)置一個(gè)哨兵節(jié)點(diǎn)dummy, 這樣所有操作完成以后返回dummy.next即可煎饼。
  *因?yàn)樾枰D(zhuǎn)m ~ n 之間的節(jié)點(diǎn)，這里可以從參考上題的解題思路校赤，剩下的就是找到 m 的前驅(qū)節(jié)點(diǎn)和n的后驅(qū)節(jié)點(diǎn)的問題并且保持其中的指向
  *位置互換即可
  *邊界條件：head == null 和 m >= n
  */
   public ListNode reverseBetween(ListNode head, int m, int n) {
         //邊界條件的處理
       if(head == null || m>=n){
           return head;
       }
        // 設(shè)置哨兵節(jié)點(diǎn)
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;
        //找到m的前驅(qū)節(jié)點(diǎn)
        for(int i = 1 ;i < m;i++){
            head = head.next;
        }
        //必要的節(jié)點(diǎn)信息
        ListNode prevM = head;
        ListNode mNode = head.next;
        ListNode nNode = mNode;
        ListNode suffN = nNode.next;
        //翻轉(zhuǎn)m ~ n之間的節(jié)點(diǎn)
        for(int i = m ;i < n;i++){
            ListNode next = suffN.next;
            suffN.next = nNode;
            // 節(jié)點(diǎn)整體后移1位
            nNode = suffN;
            suffN = next;
        }

        //互換m和n的位置
        prevM.next = nNode;
        mNode.next = suffN;
        return dummy.next;
}
  

深度拷貝帶隨機(jī)指針的鏈表

給你一個(gè)長(zhǎng)度為 n 的鏈表吆玖，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針 random 筒溃，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。

構(gòu)造這個(gè)鏈表的 深拷貝沾乘。 深拷貝應(yīng)該正好由 n 個(gè) 全新 節(jié)點(diǎn)組成怜奖，其中每個(gè)新節(jié)點(diǎn)的值都設(shè)為其對(duì)應(yīng)的原節(jié)點(diǎn)的值。新節(jié)點(diǎn)的 next 指針和 random 指針也都應(yīng)指向復(fù)制鏈表中的新節(jié)點(diǎn)翅阵，并使原鏈表和復(fù)制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)歪玲。復(fù)制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點(diǎn) 。

例如掷匠，如果原鏈表中有 X 和 Y 兩個(gè)節(jié)點(diǎn)滥崩，其中 X.random --> Y 。那么在復(fù)制鏈表中對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn) x 和 y 槐雾，同樣有 x.random --> y 叠纷。

返回復(fù)制鏈表的頭節(jié)點(diǎn)灌危。

用一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的鏈表來表示輸入/輸出中的鏈表贰您。每個(gè)節(jié)點(diǎn)用一個(gè) [val, random_index] 表示：

val：一個(gè)表示 Node.val 的整數(shù)鳖悠。
random_index：隨機(jī)指針指向的節(jié)點(diǎn)索引（范圍從 0 到 n-1）敏沉；如果不指向任何節(jié)點(diǎn)饼问，則為 null 骑素。
你的代碼 只 接受原鏈表的頭節(jié)點(diǎn) head 作為傳入?yún)?shù)鲫忍。

示例 1：

復(fù)制帶隨機(jī)指針的鏈表-示例1

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

復(fù)制帶隨機(jī)指針的鏈表-示例2

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]
示例 3：

復(fù)制帶隨機(jī)指針的鏈表-示例3

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]
示例 4：

輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指針）逐抑，因此返回 null鸠儿。

提示：

0 <= n <= 1000
-10000 <= Node.val <= 10000
Node.random 為空（null）或指向鏈表中的節(jié)點(diǎn)。

/**
思路1：1.邊界條件處理
2.通過Map 保存1 和 1‘ 的對(duì)應(yīng)關(guān)系
3. 復(fù)制原鏈表的指向關(guān)系厕氨。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    private Map<Node,Node> nodeMap = new HashMap<Node,Node>();

    public Node copyRandomList(Node head) {
        /**
         *思路1：1. 使用一個(gè)集合來存儲(chǔ)head和head‘的對(duì)應(yīng)關(guān)系进每。
         *      2. 仿照head 配置head’
         */
         //邊界條件處理：判斷是非為空
        if(head == null){
            return head;
        }
        Node dummy = new Node(-10001);
        dummy.next = head;
        // 循環(huán)獲取head‘
        while(head != null){
            Node newHead = new Node(head.val);   
            nodeMap.put(head,newHead);
            head = head.next;
        }
        // 復(fù)制next和random的關(guān)系
        for (Map.Entry<Node,Node> entry : nodeMap.entrySet()) {
            entry.getValue().next = nodeMap.get(entry.getKey().next);
            entry.getValue().random = nodeMap.get(entry.getKey().random);
        }

        return nodeMap.get(dummy.next);  
    }
}

//思路2：在原鏈表中維護(hù)1和1‘的指向關(guān)系。具體如下：
//原鏈表：1 -> 2 -> 3
//現(xiàn)在鏈表：1 -> 1' -> 2 ->2' -> 3 -> 3'(目的：維護(hù)1和1’的關(guān)系)
//將復(fù)制后的鏈路拆分出來命斧，并且還原原來的引用關(guān)系田晚。
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        //思路2：在原鏈表中維護(hù)1和1‘的指向關(guān)系。具體如下：
        //原鏈表：1 -> 2 -> 3
        //現(xiàn)在鏈表：1 -> 1' -> 2 ->2' -> 3 -> 3'(目的：維護(hù)1和1’的關(guān)系)
        //將復(fù)制后的鏈路拆分出來国葬，并且還原原來的引用關(guān)系贤徒。

        //邊界條件的處理
        if(head == null){
            return head;
        }
        //新鏈表：1 -> 1' -> 2 ->2' -> 3 -> 3'
        copy(head);
        
        copyRandom(head);

        return split(head);

    }
    /**
     * 將新鏈表的節(jié)點(diǎn),copy到原鏈表對(duì)應(yīng)節(jié)點(diǎn)的next節(jié)點(diǎn)上。
     */
    private void copy(Node head){
        Node copyNextNode = head;
        while(copyNextNode != null){
            Node copyNode  = new Node(copyNextNode.val);

            copyNode.next = copyNextNode.next;
            copyNextNode.next =copyNode;
            // 移位操作
            copyNextNode = copyNode.next;
        }
    }

    /**
     * 根據(jù)原來鏈表的random 復(fù)制新鏈表的random
     */
    private void copyRandom(Node head){
        Node copyRandomNode  = head;

        while(copyRandomNode != null && copyRandomNode.next != null){

            if(copyRandomNode.random != null){
                copyRandomNode.next.random = copyRandomNode.random.next;
            }else{
                copyRandomNode.next.random =  null;
            }
            //移位操作
            copyRandomNode = copyRandomNode.next.next;
        }

    }
    /**
     * 拆分成兩個(gè)鏈表汇四，并保證兩個(gè)鏈表指向的正確性
     */
    private Node split(Node head){
        Node node  = head;
        Node result = node.next;

        while(node != null && node.next != null){
            Node nextNode = node.next.next; 
            Node copyNode = node.next;
            
            if(copyNode != null && nextNode != null){
                node.next = nextNode;
                copyNode.next = nextNode.next;
            }else{
                node.next = null;
                copyNode.next = null;
            }
            //移位操作
            node = nextNode;
        }
        return result;
    }
}

鏈表相加

給你兩個(gè) 非空 的鏈表接奈，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的通孽，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字序宦。

請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表背苦。

你可以假設(shè)除了數(shù)字 0 之外互捌，這兩個(gè)數(shù)都不會(huì)以 0 開頭堡僻。

示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.
示例 2：

輸入：l1 = [0], l2 = [0]
輸出：[0]
示例 3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

提示：

每個(gè)鏈表中的節(jié)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
0 <= Node.val <= 9
題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //思路1：分別對(duì)兩個(gè)數(shù)組遍歷求和，然后相加疫剃，最后將結(jié)果替換成鏈表钉疫。
        //優(yōu)點(diǎn)：簡(jiǎn)單高效
        //缺點(diǎn)：無法滿足提示條件，即long類型對(duì)結(jié)果無法存儲(chǔ)

        // 思路2：鏈表相應(yīng)位置依次相加求和巢价，將進(jìn)位進(jìn)行存儲(chǔ)牲阁，用于下次相加計(jì)算,所以操作執(zhí)行完成返回最終鏈表-- 即返回最終鏈表的頭即可。
        //優(yōu)點(diǎn)：無序考慮數(shù)據(jù)求和存儲(chǔ)問題壤躲。
        // 缺點(diǎn)：編碼復(fù)雜
        // 正常條件：l1 != null 且l2 != null;
        //邊界條件包括：l1 == null; l2 == null; l1 == null的時(shí)候l2 != null;l2 == null的時(shí)候l1 != null; 最近循環(huán)完成進(jìn)位值 != 0
        // 優(yōu)化點(diǎn)：哨兵節(jié)點(diǎn)

        if(l1 == null){
            return l2;
        }

        if(l2 == null){
            return l1;
        }
        //進(jìn)位值
        int carry = 0;
        // 設(shè)置哨兵節(jié)點(diǎn)
        ListNode sentry = new ListNode(-1);
        ListNode pre = sentry;

        while(l1 != null && l2 != null){
            int number = l1.val + l2.val + carry;

            carry = number/10;
            int sum = number%10;
            
            ListNode node = new ListNode(sum);

            pre.next = node;

            pre = pre.next;
            l1 = l1.next;
            l2 = l2.next;
        } 

        while(l1 != null){
            int number = l1.val + carry;

            carry = number/10;
            int sum = number%10;
            
            ListNode node = new ListNode(sum);
            pre.next = node;

            pre = pre.next;
            l1 = l1.next;
        }

        while(l2 != null){
            int number = l2.val + carry;

            carry = number/10;
            int sum = number%10;
            
            ListNode node = new ListNode(sum);
            pre.next = node;

            pre = pre.next;
            l2 = l2.next;
        }
        //循環(huán)完成進(jìn)位值 != 0
        if(carry != 0){    
            ListNode node = new ListNode(carry);
            pre.next = node;
        }
        return sentry.next;

    }
}

[圖片上傳失敗...(image-172d9f-1615721932866)]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
              if(l1 == null){
            return l2;
        }

        if(l2 == null){
            return l1;
        }
        int carry = 0;
          //哨兵節(jié)點(diǎn)  
        ListNode head = new ListNode(-1);

        ListNode pre = head;
        while(l1 != null || l2 != null){

            l1 = l1 == null?new ListNode(0):l1;
            l2 = l2 == null?new ListNode(0):l2;

            int number = l1.val + l2.val + carry;

            carry = number/10;
            int sum = number%10;

            ListNode node = new ListNode(sum);
            pre.next = node;
        
            pre = pre.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        if(carry != 0){
            ListNode node = new ListNode(carry);
            pre.next = node;
        }
              //返回生成的鏈表--即返回真正的頭結(jié)點(diǎn)
        return head.next;
    }
}

如果字符串是通過單鏈表來存儲(chǔ)的城菊，那該如何來判斷是一個(gè)回文串呢？

跳表

概念

鏈表加多級(jí)索引結(jié)構(gòu)碉克。

優(yōu)點(diǎn)

1. 支持快速插入凌唬，刪除，查找操作漏麦，編寫代碼要求低客税，時(shí)間復(fù)雜度：O(logn).
2. 實(shí)現(xiàn)非常靈活，可以通過改變索引構(gòu)建策略撕贞，有效平衡執(zhí)行效率和內(nèi)存消耗更耻。
3. 為了代碼的簡(jiǎn)單、易讀捏膨，會(huì)用跳表替代紅黑樹秧均。