leetcode上關于單向鏈表的《反轉鏈表》求解步驟及思路(C語言)

##1.《反轉鏈表》 ——《劍指Offer》

題干如下:

題目所給介面如下：

解題：
方法一：——定義三個指標，一步步迭代將鏈表逆置

思路：既然想要逆置，很好的就可以想到定義兩個指標來指向這個鏈表的頭和頭的下一個節點，因為這樣的話，我們只需讓n2 -> next = n1；即可完成這兩個鏈表的逆置

n2->next = n1;//完成1 和 2 的逆置

但這樣想了想，好像有點不太對勁，
因為我們這樣做的話，我們就找不到 3 了

很自然的我們可以想到再去定義一個指標來指向 3 這樣，就可以保留住 3 的地址，讓我們可以迭代下去，

整理好思路后，得到下面的圖:

我們讓 n1 指向 NULL , n2 指向我們的head ,n3指向head->next（也即head的下一個元素的地址)
這樣的話！：
讓我們的n2 指向 n1 (開始為空) ，然后開始迭代起來，

讓 n1 替代 上一次 n2的位置，n2替代 上一次 n3 的位置 n3替代n3的下一個位置
這樣，就跑起來了

當然，資料結構嘛，某大神說過要如履薄冰~ 這里要考慮別的情況發生
如果這個鏈表為空怎么辦？

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
	struct ListNode * n1 = NULL,*n2 = head,*n3=head->next;
	//這里有錯誤
}

那么這里的n3不就在訪問空指標了？

考慮到這個問題就很好解決了，多加一個限制判斷條件就行了~

struct ListNode* reverseList(struct ListNode* head){
	if (head == NULL || head->next == NULL)//如果鏈表為慷訓者只有一個
		return head;
	struct ListNode * n1 = NULL, *n2 = head, *n3 = head->next;
}

還需要注意到一點，凡是遇到迭代，一定要考慮的是什么時候停止迭代

這里一定要慎重！慎重！（因為我第一次提交就在這栽了）
一定不是n3 == NULL 時才停止，因為在n3指向空時，n2還可以指向n1，他們兩個中的val還有啊！所以，限定條件應該是 while(n2) 也即 n2不為空時 很好想，當n2為空時，就沒有可以逆置的必要了，

畫完圖了也整理好思路了，特殊情況也考慮到位了，那么我們開始吧

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
}  
    if(head == NULL || head->next == NULL)//如果鏈表為空，或者只有一個的話
    return head;

    struct ListNode * n1 = NULL, * n2 = head, * n3 = head->next; 
    
    while(n2)
    {
        //反轉
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
    }
    return n1;
}

運行一下~

啊這，，出現了空指標的報錯，，
（還好leetcode不像牛客，給了報錯提示）

出現了什么問題？其實很好想，這還是我沒有考慮全面所導致的
n3已經到達了最后，指向NULL了
我這個時候再去訪問它，這不是在訪問空指標嘛！
改！改！改！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){

    if(head == NULL || head->next == NULL)//如果鏈表為空，或者只有一個的話
    return head;

    struct ListNode * n1 = NULL, * n2 = head, * n3 = head->next; 
    
    while(n2)
    {
        //反轉
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        if(n3)//在這判斷一下，如果n3不為空的話才進行下一步迭代~
        n3 = n3->next;
    }
    return n1;
}

走你~

方法二：——利用頭插

這個方法個人很喜歡，因為頭插這個方法很好就想到了

思路：舉個例子，上圖的例子1至5直到NULL
要想讓它們逆置，將上面的數字一一拿下來頭插，不就搞定了~

思路有了，代碼就好寫了：

首先先設定一個新的頭節點 newhead 先讓它指向空（NULL），然后開始頭插

設定cur和next兩個節點，指向第一個節點和第二個節點
至于為什么要設定next,是因為待會頭插的時候，將cur拿去指向newhead后，你還得遍歷到第二個節點（也即將cur移到2)，但是如果沒有next，你并不能得到指向2的指標，

懂得頭插的同學都知道，將cur挪下來之后，要讓他成為新的頭節點，然后接著移動cur，

然后接著套娃，將現在的cur再挪下來當頭，然后cur再繼續遍歷

好了好了，那么終止條件呢？

當迭代到這一步的時候，似乎可以一眼就看出來，當cur等于空時，所有的節點都進行過一次頭插了，
那么限制條件就是 while(cur)

思路整理清楚了，有需要什么我們值得考慮的地方嗎？
如果這個鏈表為空，或者只有一個節點呢？
我們先放出代碼：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode * newhead = NULL;
    struct ListNode * cur = head;
    while(cur)
    {
        struct ListNode * next = cur->next;
        cur->next = newhead;//頭插
        newhead = cur;

        cur = next;//迭代
    }
    return newhead;
}

似乎沒啥問題，cur一開始就指向我們的head,而如果鏈表為空，那么就是說cur指向NULL,那么回圈壓根進不去，直接回傳newhead;
跑一下試試！

呼舒服了~

博主能力弱QAQ
如各位大佬發現錯誤請及時糾正和批評~