C++實(shí)現(xiàn)LeetCode(206.倒置鏈表)

更新時(shí)間：2021年08月06日 16:30:04 作者：Grandyang

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

[LeetCode] 206.Reverse Linked List 倒置鏈表

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

之前做到 Reverse Linked List II 的時(shí)候我還納悶怎么只有二沒有一呢，原來真是忘了啊，現(xiàn)在才加上，這道題跟之前那道比起來簡(jiǎn)單不少，題目為了增加些許難度，讓我們分別用迭代和遞歸來實(shí)現(xiàn)，但難度還是不大。我們先來看迭代的解法，思路是在原鏈表之前建立一個(gè)空的newHead，因?yàn)槭坠?jié)點(diǎn)會(huì)變，然后從head開始，將之后的一個(gè)節(jié)點(diǎn)移到newHead之后，重復(fù)此操作直到head成為末節(jié)點(diǎn)為止，代碼如下：

解法一：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newHead = NULL;
        while (head) {
            ListNode *t = head->next;
            head->next = newHead;
            newHead = head;
            head = t;
        }
        return newHead;
    }
};

下面我們來看遞歸解法，代碼量更少，遞歸解法的思路是，不斷的進(jìn)入遞歸函數(shù)，直到head指向倒數(shù)第二個(gè)節(jié)點(diǎn)，因?yàn)閔ead指向空或者是最后一個(gè)結(jié)點(diǎn)都直接返回了，newHead則指向?qū)ead的下一個(gè)結(jié)點(diǎn)調(diào)用遞歸函數(shù)返回的頭結(jié)點(diǎn)，此時(shí)newHead指向最后一個(gè)結(jié)點(diǎn)，然后head的下一個(gè)結(jié)點(diǎn)的next指向head本身，這個(gè)相當(dāng)于把head結(jié)點(diǎn)移動(dòng)到末尾的操作，因?yàn)槭腔厮莸牟僮鳎詇ead的下一個(gè)結(jié)點(diǎn)總是在上一輪被移動(dòng)到末尾了，但head之后的next還沒有斷開，所以可以順勢(shì)將head移動(dòng)到末尾，再把next斷開，最后返回newHead即可，代碼如下：

解法二：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }
};

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

您可能感興趣的文章: