C++進(jìn)階練習(xí)刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn)詳解

更新時(shí)間：2022年05月19日 09:45:28 作者：Demo龍

這篇文章主要給大家介紹了關(guān)于如何利用C++刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn),文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

1.鏈接

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

2.題目描述

3.解題思路

方法一

1.在對(duì)鏈表進(jìn)行操作時(shí)，一種常用的技巧是添加一個(gè)啞節(jié)點(diǎn)（dummy node），它的 next指針指向鏈表的頭節(jié)點(diǎn)。這樣一來(lái)，我們就不需要對(duì)頭節(jié)點(diǎn)進(jìn)行特殊的判斷了。

例如，在本題中，如果我們要?jiǎng)h除節(jié)點(diǎn) y，我們需要知道節(jié)點(diǎn) y 的前驅(qū)節(jié)點(diǎn) x，并將 x 的指針指向 y 的后繼節(jié)點(diǎn)。

但由于頭節(jié)點(diǎn)不存在前驅(qū)節(jié)點(diǎn)，因此我們需要在刪除頭節(jié)點(diǎn)時(shí)進(jìn)行特殊判斷。但如果我們添加了啞節(jié)點(diǎn)，那么頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是啞節(jié)點(diǎn)本身，此時(shí)我們就只需要考慮通用的情況即可。特別地，在某些語(yǔ)言中，由于需要自行對(duì)內(nèi)存進(jìn)行管理。因此在實(shí)際的面試中，對(duì)于「是否需要釋放被刪除節(jié)點(diǎn)對(duì)應(yīng)的空間」這一問題，我們需要和面試官進(jìn)行積極的溝通以達(dá)成一致。下面的代碼中默認(rèn)不釋放空間。

一種容易想到的方法是，我們首先從頭節(jié)點(diǎn)開始對(duì)鏈表進(jìn)行一次遍歷，得到鏈表的長(zhǎng)度 L。隨后我們?cè)購(gòu)念^節(jié)點(diǎn)開始對(duì)鏈表進(jìn)行一次遍歷，當(dāng)遍歷到第 L−n+1 個(gè)節(jié)點(diǎn)時(shí)，它就是我們需要?jiǎng)h除的節(jié)點(diǎn)。為了方便刪除操作，我們可以從啞節(jié)點(diǎn)開始遍歷 L−n+1 個(gè)節(jié)點(diǎn)。當(dāng)遍歷到第 L−n+1 個(gè)節(jié)點(diǎn)時(shí)，它的下一個(gè)節(jié)點(diǎn)就是我們需要?jiǎng)h除的節(jié)點(diǎn)，這樣我們只需要修改一次指針，就能完成刪除操作。

方法二

我們可以設(shè)想假設(shè)設(shè)定了雙指針 p 和 q 的話，當(dāng) q 指向末尾的 NULL，p 與 q 之間相隔的元素個(gè)數(shù)為 n 時(shí)，那么刪除掉 p 的下一個(gè)指針就完成了要求。

設(shè)置虛擬節(jié)點(diǎn) dummyHead 指向 head

設(shè)定雙指針 p 和 q，初始都指向虛擬節(jié)點(diǎn) dummyHead

移動(dòng) q，直到 p 與 q 之間相隔的元素個(gè)數(shù)為 n

同時(shí)移動(dòng) p 與 q，直到 q 指向的為 NULL

將 p 的下一個(gè)節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)

4.題解

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

方法二

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
     ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }
        while(q){
            p = p->next;
            q = q->next;
        }
        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;
        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        return retNode;
    }
};

到此這篇關(guān)于C++進(jìn)階練習(xí)刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn)詳解的文章就介紹到這了,更多相關(guān)C++刪除鏈表節(jié)點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: