目錄

1? 基礎(chǔ)知識(shí)

1.1? 空指針

1.2? 結(jié)構(gòu)體

1.3? 指針訪問

1.4? 三目運(yùn)算符

2? 160. 相交鏈表

3? 206. 反轉(zhuǎn)鏈表

4? 234. 回文鏈表

菜鳥做題第三周，語言是 C++

1? 基礎(chǔ)知識(shí)

1.1? 空指針

使用 nullptr 來判斷是否為空指針：

if (headA == nullptr)

“NULL 在 C++ 中就是 0，這是因?yàn)樵?C++ 中 void* 類型是不允許隱式轉(zhuǎn)換成其他類型的，所以之前 C++ 中用 0 來代表空指針，但是在重載整型的情況下，會(huì)出現(xiàn)上述的問題。所以，C++11 加入了 nullptr，可以保證在任何情況下都代表空指針，而不會(huì)出現(xiàn)上述的情況，因此，建議以后還是都用 nullptr 替代 NULL 吧，而 NULL 就當(dāng)做 0 使用。”

摘自博客：C++ 中 NULL 和 nullptr 的區(qū)別

1.2? 結(jié)構(gòu)體

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

• val 和 next 都是結(jié)構(gòu)體 ListNode 中的元素
• val 表示當(dāng)前鏈表節(jié)點(diǎn)的值
• next 表示指向下一個(gè)鏈表節(jié)點(diǎn)的指針
• ListNode(int x) : val(x), next(NULL) {} 是初始化方法

1.3? 指針訪問

ListNode * p;

p->val;  // 訪問值
p->next;  // 訪問下一節(jié)點(diǎn)指針

1.4? 三目運(yùn)算符

pA = pA == nullptr ? headB : pA->next;

其中，“?” 前的是判斷條件，“?” 后的是兩個(gè)選項(xiàng)，“:” 前的是條件成立時(shí)選擇的選項(xiàng)，“:” 后的是條件不成立時(shí)選擇的選項(xiàng)。這里的 “pA == nullptr” 是判斷條件，“headB” 是 “pA == nullptr” 成立時(shí) “pA” 等于的值，“pA->next” 是 “pA == nullptr” 不成立時(shí) “pA” 等于的值。

三目運(yùn)算符不是為了裝逼用的，真的可以在很多情況下簡化判斷結(jié)構(gòu)。

2? 160. 相交鏈表

媽呀，這是我大一下程算課期末的真題

解題思路：

假設(shè)藍(lán)色段的長度為 a，綠色段的長度為 b，黃色段的長度為 c 。定義 pA 和 pB 兩個(gè)指針，pA 遍歷完 a + c 后遍歷 b，pB 遍歷完 b + c 后遍歷 a，判斷：

• 若 pA 和 pB 相遇且節(jié)點(diǎn)不為空，則表明兩條鏈表相交
• 若 pA 和 pB 未相遇或節(jié)點(diǎn)為空，則表明兩條鏈表不相交

這種解法用到了一點(diǎn)數(shù)學(xué)思想：

即 pA 和 pB 最終都會(huì)到達(dá)同一位置，它們?cè)谠撐恢弥赶虻墓?jié)點(diǎn)是否一致決定了鏈表是否相交。

如有疑問請(qǐng)參考官方題解，它的分情況討論更加詳細(xì)。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode * pA = headA, * pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

3? 206. 反轉(zhuǎn)鏈表

解題思路：把所有節(jié)點(diǎn)的 next 指針全部反向即可。

思路說明圖：

對(duì)于這種反轉(zhuǎn)問題，核心思想就是把已經(jīng)遍歷過的、但還需要用到的位置保存下來。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * prev = nullptr;
        ListNode * curr = head;
        while (curr) {
            ListNode * next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        } 
        return prev;
    }
};

4? 234. 回文鏈表

解題思路：文章來源地址http://www.zghlxwxcb.cn/news/detail-827481.html

1. 遍歷鏈表，把所有 val 存入一個(gè)數(shù)組中
2. 遍歷數(shù)組的前半段，判斷里面的 val 是否和后半段的 val 對(duì)稱

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode * p = head;
        vector<int> vals;
        while (p) {
            vals.push_back(p->val);
            p = p->next;
        }

        for (int i = 0; i < vals.size() / 2 + 1; ++i) {
            if (vals[i] != vals[vals.size() - i - 1]) return false;
        }
        return true;
    }
};

到了這里，關(guān)于LeetCode 熱題 100 | 鏈表（上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！