題目鏈接

• 我的代碼

  • • 簡評：

• 法一

  • • 思路：

• 法二

  • • 思路：

我的代碼

簡評：

沒啥邏輯。。。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == nullptr || pHead->next == nullptr)
            return pHead;
        ListNode *h1 = pHead, *h2 = pHead->next, *h3 = pHead->next->next;
        pHead->next = nullptr;
        while(h3 != nullptr) {
            h2->next = h1;
            h1 = h2;
            h2 = h3;
            h3 = h3->next;
        }
        h2->next = h1;
        return h2;
    }
};

法一

思路：

作者：?？皖}霸
初始化：3個指針
1）pre指針指向已經(jīng)反轉(zhuǎn)好的鏈表的最后一個節(jié)點，最開始沒有反轉(zhuǎn)，所以指向nullptr
2）cur指針指向待反轉(zhuǎn)鏈表的第一個節(jié)點，最開始第一個節(jié)點待反轉(zhuǎn)，所以指向head
3）nex指針指向待反轉(zhuǎn)鏈表的第二個節(jié)點，目的是保存鏈表，因為cur改變指向后，后面的鏈表則失效了，所以需要保存
接下來，循環(huán)執(zhí)行以下三個操作
1）nex = cur->next, 保存作用
2）cur->next = pre 未反轉(zhuǎn)鏈表的第一個節(jié)點的下個指針指向已反轉(zhuǎn)鏈表的最后一個節(jié)點
3）pre = cur， cur = nex; 指針后移，操作下一個未反轉(zhuǎn)鏈表的第一個節(jié)點
循環(huán)條件，當(dāng)然是cur != nullptr
循環(huán)結(jié)束后，cur當(dāng)然為nullptr，所以返回pre，即為反轉(zhuǎn)后的頭結(jié)點

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex = nullptr; // 這里可以指向nullptr，循環(huán)里面要重新指向
        while (cur) {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};

法二

思路：

構(gòu)造鏈表
如果此類型的題出現(xiàn)在筆試中，如果內(nèi)存要求不高，可以采用如下方法：
可以先用一個vector將單鏈表的指針都存起來，然后再構(gòu)造鏈表。
此方法簡單易懂，代碼好些。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (!pHead) return nullptr;
        vector<ListNode*> v;
        while (pHead) {
            v.push_back(pHead);
            pHead = pHead->next;
        }
        reverse(v.begin(), v.end()); // 反轉(zhuǎn)vector，也可以逆向遍歷
        ListNode *head = v[0];
        ListNode *cur = head;
        for (int i=1; i<v.size(); ++i) { // 構(gòu)造鏈表
            cur->next = v[i]; // 當(dāng)前節(jié)點的下一個指針指向下一個節(jié)點
            cur = cur->next; // 當(dāng)前節(jié)點后移
        }
        cur->next = nullptr; // 切記最后一個節(jié)點的下一個指針指向nullptr
        return head;
    }
};