精品亚洲在线观看国产,在线免费视频AAA,92国产精品

今日學(xué)習(xí)的視頻和文章

代碼隨想錄鏈表基礎(chǔ)
代碼隨想錄兩兩交換鏈表的節(jié)點(diǎn)
代碼隨想錄刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)
代碼隨想錄鏈表相交
代碼隨想錄環(huán)形鏈表II
王道數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo) 鏈表部分王道計算機(jī)考研數(shù)據(jù)結(jié)構(gòu)_嗶哩嗶哩_bilibili

LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)

24. 兩兩交換鏈表中的節(jié)點(diǎn) - 力扣（Leetcode）

經(jīng)過對鏈表知識的復(fù)習(xí)以及對“虛擬節(jié)點(diǎn)”思想的理解，這道題目初見時我寫起來感覺比較簡單，只需要添加一個虛擬頭節(jié)點(diǎn)，然后模擬各個節(jié)點(diǎn)的next的調(diào)整過程即可。
我初見的題解和代碼隨想錄的題解比起來還是有差距的，其實(shí)不需要left、pre等這么多保留臨時節(jié)點(diǎn)的變量，是否需要保留臨時節(jié)點(diǎn)，應(yīng)該根據(jù)各個節(jié)點(diǎn)的next的調(diào)整過程來判斷，如果調(diào)整過程中還能取到這個節(jié)點(diǎn)，則可以不需要保留臨時節(jié)點(diǎn)?？梢姡看窝h(huán)中cur的選取，以及各個節(jié)點(diǎn)的next的調(diào)整順序，對于代碼實(shí)現(xiàn)的影響是很大的。

image.png

初見題目的完整題解代碼如下

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;
    ListNode* left = dummyHead;
    ListNode* pre = dummyHead->next;
    ListNode* cur = head ? head->next : nullptr;
    ListNode* next = nullptr;
    while (cur) {
        left->next = cur;
        next = cur->next;
        cur->next = pre;
        pre->next = next;

        left = pre;
        pre = next;
        cur = next ? next->next : nullptr;
    }
    head = dummyHead->next;
    delete dummyHead;
    return head;
}

而代碼隨想錄的cur選取是兩兩交換的一組節(jié)點(diǎn)的前一個節(jié)點(diǎn)，顯然需要兩兩交換的節(jié)點(diǎn)都可以用cur取到，只需要暫存cur->next即可。

image.png

代碼隨想錄給出的題解代碼：

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(0); // 設(shè)置一個虛擬頭結(jié)點(diǎn)
    dummyHead->next = head; // 將虛擬頭結(jié)點(diǎn)指向head，這樣方面后面做刪除操作
    ListNode* cur = dummyHead;
    while(cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* tmp = cur->next; // 記錄臨時節(jié)點(diǎn)
        ListNode* tmp1 = cur->next->next->next; // 記錄臨時節(jié)點(diǎn)

        cur->next = cur->next->next;    // 步驟一
        cur->next->next = tmp;          // 步驟二
        cur->next->next->next = tmp1;   // 步驟三

        cur = cur->next->next; // cur移動兩位，準(zhǔn)備下一輪交換
    }
    return dummyHead->next;
}

看了講解之后改良的題解代碼，其實(shí)還可以再少保存一個臨時節(jié)點(diǎn)，只需要暫存cur->next即可：

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;
    ListNode* cur = dummyHead;
    while (cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* temp = cur->next;
        // 讓節(jié)點(diǎn)cur的next指向節(jié)點(diǎn)2
        cur->next = cur->next->next;
        
        // 此時節(jié)點(diǎn)2的next還指向節(jié)點(diǎn)3，所以可以用來讓節(jié)點(diǎn)1的next來指向節(jié)點(diǎn)3
        temp->next = cur->next->next;
        
        // 讓節(jié)點(diǎn)2的next指向節(jié)點(diǎn)1
        cur->next->next = temp;
        
        // cur指向節(jié)點(diǎn)1，嘗試進(jìn)入下一次交換
        cur = temp;
    }
    head = dummyHead->next;
    delete dummyHead;
    return head;
}

上述題解對應(yīng)的模擬步驟和代碼隨想錄的步驟有所不同，示意如下：

image.png

LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)

19. 刪除鏈表的倒數(shù)第 N 個結(jié)點(diǎn) - 力扣（Leetcode）

初見題目時的想法：鏈表長度未知，先遍歷一遍得到鏈表長度，再算出要刪除的節(jié)點(diǎn)的位置。

題解代碼如下：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    int size = 0;
    ListNode* cur = head;
    while (cur) {
        cur = cur->next;
        size++;
    }

    int target = size - n;
    cur = dummyHead;
    while (target--) {
        cur = cur->next;
    }
    cur->next = cur->next->next;

    head = dummyHead->next;
    delete dummyHead;
    return head;
}

看到題目提示能不能只用一遍掃描來完成，思路如下：
- 首先，倒數(shù)第n個節(jié)點(diǎn)和最后一個節(jié)點(diǎn)的位置距離固定為n，那么，可以用一個長度為n的窗口去掃描鏈表，當(dāng)這個窗口的尾部到達(dá)了鏈表結(jié)束位置時，刪除窗口的第一個元素。
- 于是產(chǎn)生了雙指針的想法，用一個fast指針和一個slow指針來表示這個滑動的窗口。
- fast和slow相距n個節(jié)點(diǎn)，由于題目限定了n都是合理的值，就不用考慮n值是否越界了
- fast和slow一起掃描鏈表，直到fast->next指向NULL，用slow來刪除目標(biāo)節(jié)點(diǎn)。
  - 為什么是fast->next？因為要刪除一個節(jié)點(diǎn)，應(yīng)該讓slow指向倒數(shù)第n個節(jié)點(diǎn)的前一個節(jié)點(diǎn)，所以在下面的代碼里讓fast->next指向NULL時退出循環(huán)，就正好讓slow指向我們要的位置。

完整題解代碼如下：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;
    while (n--) {
        fast = fast->next;
    }
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* del = slow->next; 
    slow->next = slow->next->next;
    delete del;

    head = dummyHead->next;
    delete dummyHead;
    return head;
}

聽了一遍講解，發(fā)現(xiàn)自己這道題能考慮得比較清楚了，但還是要多復(fù)習(xí)多練習(xí)多總結(jié)。

LeetCode面試題02.07 鏈表相交

面試題 02.07. 鏈表相交 - 力扣（Leetcode）

初見題目時的想法：
- 起初最令我疑惑的地方是如何判斷從哪里開始鏈表相交，但似乎題目規(guī)定了只要A鏈表的一個節(jié)點(diǎn)的值和B鏈表的一個節(jié)點(diǎn)的值相等，則A鏈表該節(jié)點(diǎn)之后的值與B鏈表節(jié)點(diǎn)之后的值都相等，所以只需要找兩個鏈表從各自哪個節(jié)點(diǎn)的值開始相等，即可找到相交的位置。
- 然而到這里我就理解錯題意了，鏈表相交是兩個鏈表各自的某個節(jié)點(diǎn)的next指向的節(jié)點(diǎn)相同，并非值相等。
- 那么，最簡單的方法就是讓A鏈表的每個節(jié)點(diǎn)都與B鏈表的節(jié)點(diǎn)逐個比較，這樣的時間復(fù)雜度顯然是 $O(n^2)$
- 觀察題目所給的例子，相交的鏈表是從倒數(shù)的第n項開始相交的，而A鏈表和B鏈表相交之前的項的最后一個節(jié)點(diǎn)是對齊的。
- 如果A鏈表和B鏈表長度不等的話，可以從哪里開始相交呢？
  - 設(shè)A鏈表長度為 $L_A$ ，B鏈表長度為 $L_B$ ，假設(shè) $L_A>L_B$ 。
  - A鏈表是不是能包含B鏈表？就是說是否*headB指向的其實(shí)是A鏈表的某個非頭節(jié)點(diǎn)。但這里應(yīng)該是我想復(fù)雜了，題目說是兩個鏈表，如果是這種情況，應(yīng)該是不符合題意的。所以，A鏈表比B鏈表長的部分，應(yīng)該是不能與B鏈表相交的，那么節(jié)點(diǎn)的地址值的比較應(yīng)該從A鏈表的第 $L_A-L_B$ （從0開始）個節(jié)點(diǎn)開始。

完整的題解代碼如下：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;

    int lthA = 0;
    while (curA) {
        curA = curA->next;
        lthA++;
    }
    int lthB = 0;
    while (curB) {
        curB = curB->next;
        lthB++;
    }

    curA = headA;
    curB = headB;
    if (lthA < lthB) {
        swap(lthA, lthB);
        swap(curA, curB);
    }
    int align = lthA - lthB;
    while (align--) {
        curA = curA->next;
    }

    while (curA != nullptr && curB != nullptr) {
        if (curA == curB) return curA;
        curA = curA->next;
        curB = curB->next;
    }

    return nullptr;
}

LeetCode142 環(huán)形鏈表

142. 環(huán)形鏈表 II - 力扣（Leetcode）

初見題目時的想法：
- 如何判斷鏈表是否出現(xiàn)了環(huán)？我第一反應(yīng)是使用哈希表，由于每個節(jié)點(diǎn)的地址都是唯一的，所以可以以地址作為哈希表的key值來存儲已經(jīng)遍歷過的節(jié)點(diǎn)。我看到題目有進(jìn)階提示為使用O(1)的空間，但使用哈希表的話顯然使用的空間為O(n)。

使用哈希表的題解代碼：

ListNode *detectCycle(ListNode *head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    ListNode* cur = dummyHead;
    unordered_map<ListNode*, int> nodeMap;
    int index = 0;
    while (cur) {
        if (nodeMap.find(cur) != nodeMap.end()) {
            delete dummyHead;
            return cur;
        }
        else {
            nodeMap.insert({cur, index});
        }
        cur = cur->next;
    }

    return nullptr;
}

如何使用O(1)的空間來解決這道題呢，我思考了很久。然后想到了有環(huán)的話，遍歷出的節(jié)點(diǎn)地址就會有周期性。
- 在有環(huán)的情況下，以不同的方法去獲取節(jié)點(diǎn)地址，就有可能獲取相同的節(jié)點(diǎn)地址，不同的方法能獲取到相同的地址，說明有環(huán)，那么用什么樣的方法呢？
- 不同至少要有兩個方法去遍歷，因為今天的題目用過，我又想到了雙指針。以下是我初見題目時的思考
  - 不同的遍歷方式，用快慢指針來理解的話，就是slow每次移動一位，fast每次移動兩位，如果在循環(huán)中出現(xiàn)slow == fast情況，則說明有環(huán)。
  - 但我不知道如何求環(huán)的入口的位置，看了講解之后，這個求解方式確實(shí)超出我目前能力范圍，還是先理解了這道題再繼續(xù)努力吧。
我對這道題的數(shù)學(xué)證明過程的理解

image.png

slow表示slow經(jīng)過的節(jié)點(diǎn)數(shù)，fast表示fast經(jīng)過的節(jié)點(diǎn)數(shù)，x為從dummyHead到環(huán)的入口的節(jié)點(diǎn)數(shù)（不包括dummyHead），y為從環(huán)的入口到相遇的位置的節(jié)點(diǎn)數(shù)，z表示從相遇的位置到環(huán)的入口的節(jié)點(diǎn)數(shù)。
由于fast每次經(jīng)過2個節(jié)點(diǎn)，slow每次經(jīng)過1個節(jié)點(diǎn)，所以可以得到：
$2(x+y)=x+y+n(y+z)(n \ge 1)$
上式變形得

$x=(n-1)(y+z)+z(n \ge 1)$

到這一步，我是這樣理解的：
- 假設(shè)有一個index1從dummyHead開始每次移動一個節(jié)點(diǎn)，index1移動到環(huán)的入口經(jīng)過的節(jié)點(diǎn)數(shù)顯然為x，即上述等式的左邊。
- 有一個index2從slow和fast的相遇位置開始每次移動一個節(jié)點(diǎn)，移動到環(huán)的入口處經(jīng)過的節(jié)點(diǎn)數(shù)為(n-1)(y+z)+z，即上述等式的右邊。
- 上述等式就是說，index1與index2相遇時，index2可能在環(huán)內(nèi)轉(zhuǎn)了n-1圈。但我們現(xiàn)在不關(guān)心index2轉(zhuǎn)了幾圈，無論index2轉(zhuǎn)了幾圈，index1與index2第一次相遇時的位置一定是環(huán)的入口的位置！

完整題解代碼如下：

ListNode *detectCycle(ListNode *head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;
    while (slow != nullptr && fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = dummyHead;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

代碼隨想錄算法訓(xùn)練營Day04 | LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)、LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)、LeetCode面試題02.07 鏈表相交、LeetCode14...

代碼隨想錄算法訓(xùn)練營Day04 | LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)、LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)、LeetCode面試題02.07 鏈表相交、LeetCode14...

今日學(xué)習(xí)的視頻和文章

LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)

LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)

LeetCode面試題02.07 鏈表相交

LeetCode142 環(huán)形鏈表

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

代碼隨想錄算法訓(xùn)練營Day04 | LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)、LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)、LeetCode面試題02.07 鏈表相交、LeetCode14...

今日學(xué)習(xí)的視頻和文章

LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)

LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)

LeetCode面試題02.07 鏈表相交

LeetCode142 環(huán)形鏈表

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

代碼隨想錄算法訓(xùn)練營Day04 | LeetCode 24 兩兩交換鏈表中的節(jié)點(diǎn)、LeetCode19 刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)、LeetCode面試題02.07 鏈表相交、LeetCode14...