• LCR 024. 反轉鏈表 - 力扣（LeetCode）LCR 024. 反轉鏈表 - 給定單鏈表的頭節點 head ，請反轉鏈表，并返回反轉后的鏈表的頭節點。?示例 1：[https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg]輸入：head = [1,2,3,4,5]輸出：[5,4,3,2,1]示例 2：[https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg]輸入：head = [1,2]輸出：[2,1]示例 3：輸入：head = []輸出：[]?提示： * 鏈表中節點的數目范圍是 [0, 5000] * -5000 <= Node.val <= 5000?進階：鏈表可以選用迭代或遞歸方式完成反轉。你能否用兩種方法解決這道題？?注意：本題與主站 206?題相同：?https://leetcode-cn.com/problems/reverse-linked-list/ [https://leetcode-cn.com/problems/reverse-linked-list/]https://leetcode.cn/problems/UHnkqh/

zhe206. 反轉鏈表 - 力扣（LeetCode）?????206. 反轉鏈表 - 給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。?示例 1：[https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg]輸入：head = [1,2,3,4,5]輸出：[5,4,3,2,1]示例 2：[https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg]輸入：head = [1,2]輸出：[2,1]示例 3：輸入：head = []輸出：[]?提示： * 鏈表中節點的數目范圍是 [0, 5000] * -5000 <= Node.val <= 5000?進階：鏈表可以選用迭代或遞歸方式完成反轉。你能否用兩種方法解決這道題？https://leetcode.cn/problems/reverse-linked-list/

這兩題是一樣的

首先是三指針解法：

/*** 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) {}* };*/
/*先看題目給的定義格式，有一個val還有next*/
class Solution {
public:ListNode* reverseList(ListNode* head) {
/*傳來一個head*///先判斷鏈表為空或者鏈表數據只有一個的情況if(head==NULL||head->next==NULL)return head;//接下來我們要反轉鏈表，需要用到三個參數，就像我們之前寫數組交換數據的時候一樣//由于題目中可以看見，最后一個數據為空1->2->3->4->5->NULLstruct ListNode *n1=NULL, *n2=head ,*n3=head->next;while(n2){n2->next=n1;//反轉n1=n2;n2=n3;if(n3)n3=n3->next;}/*第一次：1->NULLn1=1,n2=2,n3=3可以看到整個數據往后移動了一位，原本是NULL,1,2第二次：2->1n1=2,n2=3,n3=4第三次：3->2n1=3,n2=4,n3=5注意 這個時候還未觸發條件，這里我們就可以看到這時候鏈表菜反轉到3，我們最后傳回的也是n1這  個頭結點第四次：4->3n1=4,n2=5,n3=NULL第五次：5->4n1=5,n2=NULL,N3=NULL到這里我們就可以看到上面的兩個判斷條件的原因1.由于最后要反轉整個鏈表，返回的是n1，對于原鏈表來說，最后一個節點是NULL反過來其實就是NULL->5而我們反轉的語句是n2->next=n1所以最后的判斷條件即為n2==NULL的時候，循環結束反轉2.最后n2==NULL的時候，n3不能再往后了，不然會出現空指針的情況，因為NULL后面沒有NULL了所以最后n3需要判斷，如果已經為空了就不需要再往后移動了*/return n1;}
};

頭插法：

/*** 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* reverseList(ListNode* head) {if(head==NULL||head->next==NULL)return head;//與上面同樣的判斷struct ListNode *cur=head , *next=head->next , *newhead=NULL;//定義三個指針，我們的目的是將newhead作為一個新的頭，通過cur一個個頭插while(cur){//同樣的還是以cur為空作為循環的判斷cur->next=newhead;newhead=cur;cur=next;//這里的判斷與上一個解法一樣if(next)next=next->next;/*第一次：cur=1,next=2,newhead=NULL將cur->next=newhead------- 1->NULL然后繼續往后走 cur=2,next=3依次類推：2->1->NULLcur=3,next=43->2->1->NULLcur=4,next=5這里就可以看出來，如果判斷條件是next==NULL，那這時的cur才等于5并且沒有插到新鏈表中所以如果cur作為5也就是最后一個數插到新鏈表中，那么它在當次循環結束后的值就為NULL即cur==NULL作為循環結束標志*/}return newhead;}
};

大家也可以動手畫一畫，我不喜歡畫圖，喜歡腦子里想，雖然我知道這不是個好習慣