前言

歡迎來到小K的Leetcode|代碼隨想錄|專題化專欄，今天將為大家?guī)矸崔D(zhuǎn)鏈表、兩兩交換鏈表中的節(jié)點(diǎn)和刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)的分享?

206. 反轉(zhuǎn)鏈表

?題目鏈接點(diǎn)這里
給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]
輸出：[2,1]

示例 3：

輸入：head = []
輸出：[]

提示：

鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 5000]
-5000 <= Node.val <= 5000

方法一：雙指針法，我們先定義一個(gè)cur節(jié)點(diǎn)指向頭結(jié)點(diǎn)，然后定義一個(gè)pre節(jié)點(diǎn)指向nullptr，然后定義一個(gè)臨時(shí)節(jié)點(diǎn)temp保存cur->next，因?yàn)槲覀円淖?code>cur->next的指向，將cur->next指向pre，循環(huán)執(zhí)行并且移動(dòng)pre和cur節(jié)點(diǎn)，當(dāng)cur指向空，循環(huán)結(jié)束，我們返回pre就OK了
如下圖，第一和第二幅圖分別展示了第一和第二步pre，cur，temp的變化以及節(jié)點(diǎn)的反轉(zhuǎn)情況，第三幅圖則代表最后一步的情況

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur)
        {
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        delete temp,cur;
        temp=nullptr,cur=nullptr;
        return pre;
    }
};

方法二：遞歸寫法，和雙指針寫法思路一樣，就是代碼看起來不是那么好理解，不過理解了雙指針，問題就不是很大

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur) 
    {
        if(cur==nullptr) return pre;
        ListNode* temp=cur->next;
        cur->next=pre;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) 
    {
        return reverse(nullptr,head);
    }
};

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

?題目鏈接點(diǎn)這里
給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

提示：

鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 100] 內(nèi)
0 <= Node.val <= 100

思路：我們通過圖解來講解我們的思路，注意我們這里引入虛擬頭結(jié)點(diǎn)，避免要單獨(dú)處理頭結(jié)點(diǎn)的情況

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        ListNode* virtualHead=new ListNode(0,head);
        ListNode* cur=virtualHead;
        while(cur->next!=nullptr&&cur->next->next!=nullptr)
        {
            ListNode* temp=cur->next;
            ListNode* temp1=cur->next->next->next;

            cur->next=cur->next->next;
            cur->next->next=temp;
            temp->next=temp1;
            
            cur=cur->next->next;
        }
        return virtualHead->next;
    }
};

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

?題目鏈接點(diǎn)這里
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例 1：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1
輸出：[]

示例 3：

輸入：head = [1,2], n = 1
輸出：[1]

提示：

鏈表中結(jié)點(diǎn)的數(shù)目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

思路：使用雙指針法，定義一個(gè)快指針和一個(gè)慢指針，讓快指針移動(dòng)n步，然后讓快指針和慢指針一起移動(dòng)，當(dāng)快指針指向空時(shí)，慢指針的指向就是要?jiǎng)h除的節(jié)點(diǎn)，這里是讓快指針移動(dòng)了n+1步，這樣最后慢指針就指向了要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)，更方便刪除

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        ListNode* virtualHead=new ListNode(0,head);
        ListNode* slow,*fast;
        slow=fast=virtualHead;
        n++;
        while(n--&&fast!=nullptr) fast=fast->next;
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return virtualHead->next;
    }
};

總結(jié)

今日為大家?guī)砹随湵淼姆崔D(zhuǎn)，節(jié)點(diǎn)的交換，節(jié)點(diǎn)的刪除這三個(gè)類型題目的分享，發(fā)現(xiàn)雙指針是用的真多！好用~愛用?文章來源地址http://www.zghlxwxcb.cn/news/detail-599125.html

到了這里，關(guān)于【代碼隨想錄 | Leetcode | 第六天】鏈表 | 反轉(zhuǎn)鏈表 | 兩兩交換鏈表中的節(jié)點(diǎn) | 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！