鏈表趣事

一說(shuō)到鏈表，就想起上學(xué)時(shí)候天馬行空的思維。記得老師第一次放出鏈表的數(shù)據(jù)結(jié)構(gòu)圖時(shí)，不知怎么的。我就想到了小時(shí)候看李連杰主演的少林寺。在戲中李連杰有件兵器，看似是長(zhǎng)棍，然后一甩成了三節(jié)棍，這個(gè)畫(huà)面一直記憶猶新。所以看到鏈表的節(jié)點(diǎn)通過(guò)指針串聯(lián)起來(lái)覺(jué)得神似。然后….這節(jié)課就沒(méi)好好學(xué)了，哈哈。

鏈表 VS 數(shù)組

提到鏈表，必然會(huì)涉及到一個(gè)話(huà)題：鏈表與數(shù)組的比較。通過(guò)兩者的對(duì)比記憶，能幫我們快速的了解一些鏈表的特性。

這里就不得不說(shuō)下數(shù)據(jù)的四種存儲(chǔ)結(jié)構(gòu)了：

1. 順序存儲(chǔ)結(jié)構(gòu)
2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
3. 散列存儲(chǔ)結(jié)構(gòu)
4. 索引存儲(chǔ)結(jié)構(gòu)

鏈表和數(shù)組是兩種截然不同的內(nèi)存組織方式，數(shù)組作為順序存儲(chǔ)結(jié)構(gòu)，使用的是連續(xù)的內(nèi)存空間，可以利用空間局部性原理，借助 CPU cache進(jìn)行預(yù)讀，所以訪(fǎng)問(wèn)效率更高。而鏈表作為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不是連續(xù)存儲(chǔ)，無(wú)法進(jìn)行緩存，隨機(jī)訪(fǎng)問(wèn)效率也較低。

但每種數(shù)據(jù)結(jié)構(gòu)，都有自己的優(yōu)劣，在這里我們需要分開(kāi)來(lái)考慮。

這里大家看到在鏈表的第三個(gè)優(yōu)點(diǎn) 插入刪除速度快 的地方我打了問(wèn)號(hào)，這是為什么？凡事不能一概而論。舉個(gè)極端的例子，我們需要分別刪除數(shù)組和鏈表的最后一個(gè)元素。而數(shù)組和鏈表的數(shù)據(jù)量巨大。這種情況下，你會(huì)認(rèn)為鏈表的刪除速度比數(shù)組快？關(guān)于這塊的知識(shí)網(wǎng)上有很多，就不做copy小能手了，大家有興趣的可以下來(lái)看看。

鏈表的題目分類(lèi)

鏈表題目一般都出在手撕算法的環(huán)節(jié)，而真正機(jī)試時(shí)很少考，為什么這么說(shuō)？

上面我們對(duì)比了鏈表和數(shù)組的關(guān)系，同樣的，鏈表的解題如果出現(xiàn)在機(jī)試中，都是可以轉(zhuǎn)化為列表進(jìn)行求解后再轉(zhuǎn)回鏈表，那所謂的刪除、逆序、兩兩交換等在鏈表中較為繁瑣的操作，通過(guò)這么轉(zhuǎn)換后還有什么難度呢？

下面來(lái)說(shuō)說(shuō)鏈表通常涉及的題目：

1. 鏈表的遍歷、插入、刪除
2. 判斷鏈表是否有環(huán)
3. 反轉(zhuǎn)鏈表系列（整體反轉(zhuǎn)、兩兩反轉(zhuǎn)等）
4. 雙鏈表、隨機(jī)指針鏈表

總體來(lái)說(shuō)鏈表的題目趨近于簡(jiǎn)單，遇到鏈表題目，初學(xué)時(shí)最重要的一點(diǎn)就是畫(huà)圖，邊畫(huà)圖邊理解才是王道。下面讓我們來(lái)看下這個(gè)系列的第一道題目吧。

劍指offerII021.刪除鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)

https://leetcode-cn.com/problems/SLwz0R/solution/shua-chuan-jian-zhi-offer-day11-lian-bia-tuyw/

難度：中等

題目：

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

提示：

• 鏈表中結(jié)點(diǎn)的數(shù)目為 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

示例：

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

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

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

分析

遇到這種題多了其實(shí)就是公式，數(shù)組中有快慢指針，鏈表同樣也可以創(chuàng)建快慢兩個(gè)指針。
初始右指針先跑N，然后左指針在和右指針開(kāi)始同步向前。
當(dāng)右指針到達(dá)末尾時(shí)：
left.next = left.next.next即可!
這里需要注意，N的取值小于等于鏈表的長(zhǎng)度。
這里就需要排除下當(dāng)右指針跑了N后，已經(jīng)超出鏈表，那么代表鏈表長(zhǎng)度與N相等。
那倒數(shù)第N個(gè)數(shù)就是鏈表頭，此時(shí)只需要返回head.next即可。
仔細(xì)分析，就是如此簡(jiǎn)單...

解題：

Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head, n):
        left = right = head
        count = 0 
        while count < n:
            right = right.next
            count += 1
        if not right:
            return head.next
        while right.next:
            left = left.next
            right = right.next
        left.next = left.next.next
        return head

Java:

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode left = head;
        ListNode right = head;
        int count = 0;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        if (right == null) {
            return head.next;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return head;
    }
}

歡迎關(guān)注我的公眾號(hào): 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)，了解更多python小知識(shí)。

我的個(gè)人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown