C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn))

更新時(shí)間：2021年07月13日 10:45:31 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 19. Remove Nth Node From End of List 移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

這道題讓我們移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)，限定n一定是有效的，即n不會(huì)大于鏈表中的元素總數(shù)。還有題目要求一次遍歷解決問題，那么就得想些比較巧妙的方法了。比如首先要考慮的時(shí)，如何找到倒數(shù)第N個(gè)節(jié)點(diǎn)，由于只允許一次遍歷，所以不能用一次完整的遍歷來統(tǒng)計(jì)鏈表中元素的個(gè)數(shù)，而是遍歷到對(duì)應(yīng)位置就應(yīng)該移除了。那么就需要用兩個(gè)指針來幫助解題，pre 和 cur 指針。首先 cur 指針先向前走N步，如果此時(shí) cur 指向空，說明N為鏈表的長(zhǎng)度，則需要移除的為首元素，那么此時(shí)返回 head->next 即可，如果 cur 存在，再繼續(xù)往下走，此時(shí) pre 指針也跟著走，直到 cur 為最后一個(gè)元素時(shí)停止，此時(shí) pre 指向要移除元素的前一個(gè)元素，再修改指針跳過需要移除的元素即可，參見代碼如下：

方式一：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head->next) return NULL;
        ListNode *pre = head, *cur = head;
        for (int i = 0; i < n; ++i) cur = cur->next;
        if (!cur) return head->next;
        while (cur->next) {
            cur = cur->next;
            pre = pre->next;
        }
        pre->next = pre->next->next;
        return head;
    }
};

方式二：

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

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

您可能感興趣的文章:

相關(guān)文章

C++實(shí)現(xiàn)簡(jiǎn)單24點(diǎn)游戲
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單24點(diǎn)游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-03-03
ubuntu系統(tǒng)下C++調(diào)用matlab程序的方法詳解
學(xué)習(xí)c++與matlab混合編程一般是通過c++調(diào)用matlab函數(shù)，因?yàn)閙atlab具有強(qiáng)大的數(shù)學(xué)函數(shù)庫，然而vc++具有界面設(shè)計(jì)靈活的優(yōu)點(diǎn)，下面這篇文章主要給大家介紹了關(guān)于在ubuntu系統(tǒng)下C++調(diào)用matlab程序的方法，需要的朋友可以參考下。
2017-08-08
c語言深入理解函數(shù)的遞歸
這一章講解的是函數(shù)的遞歸，因?yàn)檫f歸函數(shù)是一個(gè)非常重要求解復(fù)雜問題的方法之一，在學(xué)習(xí)算法的過程之中我們也會(huì)遇到他，所以我想對(duì)它進(jìn)行一次講解，希望能幫助其他人，也能幫助我自己來梳理一遍。下面我會(huì)通過一些題目的講解去認(rèn)識(shí)遞歸函數(shù)
2022-02-02
C++11中std::thread線程實(shí)現(xiàn)暫停(掛起)功能
本文主要介紹了C++11中std::thread線程實(shí)現(xiàn)暫停(掛起)功能，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2023-04-04
詳解Qt中QStackedWidget控件的使用
這篇文章主要為大家詳細(xì)介紹了Qt中QStackedWidget控件的具體使用，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下
2023-02-02
C語言實(shí)現(xiàn)時(shí)區(qū)轉(zhuǎn)換函數(shù)的實(shí)例
這篇文章主要介紹了C語言實(shí)現(xiàn)時(shí)區(qū)轉(zhuǎn)換函數(shù)的實(shí)例的相關(guān)資料,這里分析需求并提供實(shí)現(xiàn)代碼，需要的朋友可以參考下
2017-08-08
VC小技巧匯總之控件技巧
這篇文章主要介紹了VC小技巧匯總之控件技巧,對(duì)于VC的開發(fā)很有借鑒價(jià)值,需要的朋友可以參考下
2014-07-07
Qt數(shù)據(jù)庫應(yīng)用之實(shí)現(xiàn)數(shù)據(jù)的導(dǎo)入與導(dǎo)出
QT中涉及到數(shù)據(jù)庫相關(guān)的項(xiàng)目，幾乎都需要將少量的信息數(shù)據(jù)導(dǎo)出到文件保存好，然后用戶可以打開該表格進(jìn)行編輯，編輯完成后保存，再重新導(dǎo)入到軟件中。所以本文將具體為大家介紹一下這一功能如何實(shí)現(xiàn)，感興趣的可以跟隨小編一起試一試
2022-01-01
深入分析C語言存儲(chǔ)類型與用戶空間內(nèi)部分布
這篇文章主要介紹了C語言存儲(chǔ)類型與用戶空間內(nèi)部分布，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧
2022-12-12
C++實(shí)現(xiàn)獲取時(shí)間戳和計(jì)算運(yùn)行時(shí)長(zhǎng)
這篇文章主要為大家詳細(xì)介紹了如何使用C++實(shí)現(xiàn)獲取時(shí)間戳和計(jì)算運(yùn)行時(shí)長(zhǎng)功能,文中的示例代碼講解詳細(xì),有需要的小伙伴可以參考一下
2024-12-12