C++進階練習刪除鏈表的倒數(shù)第N個結(jié)點詳解

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

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

1.鏈接

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

2.題目描述

3.解題思路

方法一

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

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

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

一種容易想到的方法是，我們首先從頭節(jié)點開始對鏈表進行一次遍歷，得到鏈表的長度 L。隨后我們再從頭節(jié)點開始對鏈表進行一次遍歷，當遍歷到第 L−n+1 個節(jié)點時，它就是我們需要刪除的節(jié)點。為了方便刪除操作，我們可以從啞節(jié)點開始遍歷 L−n+1 個節(jié)點。當遍歷到第 L−n+1 個節(jié)點時，它的下一個節(jié)點就是我們需要刪除的節(jié)點，這樣我們只需要修改一次指針，就能完成刪除操作。

方法二

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

設置虛擬節(jié)點 dummyHead 指向 head

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

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

同時移動 p 與 q，直到 q 指向的為 NULL

將 p 的下一個節(jié)點指向下下個節(jié)點

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;
    }
};