这里使用两种方式，
一个是直接从头往后遍历 ——-> 迭代
一个是从最后一个往前遍历 —–> 递归
定义三个变量：pPre pNext pNow
pPre表示当前节点的前一个地址，pNext表示当前节点的下一个地址，pNow表示当前节点的地址。
反转的核心：就是把 pNow的next指针，指向 pPre
因为反转之后，pNow的next原来的值会丢，所以在反转之前，要用pNext把原来的值保存一下。
反转之后，要处理下一个节点，而本节点就是下一个节点的前一个节点，所以用pPre把当前节点地址保存一下。
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *pstPre = NULL;
struct ListNode *pstNow = head;
struct ListNode *pstNext = NULL;
while (NULL != pstNow)
{
pstNext = pstNow->next; // 先保存一下当前节点的next指针
pstNow->next = pstPre; // 做反转
pstPre = pstNow; // 更新pstPre指针
pstNow = pstNext; // 继续做下一个节点的反转
}
return pstPre;
}
递归的话，不太好理解，先上代码，看着代码来理解：
struct ListNode* reverseList(struct ListNode* head){
struct ListHode *pstNewHead = NULL;
if (head == NULL || head->next == NULL) // 如果链表为空，或者是最末端节点，则直接返回当前节点地址
{
return head;
}
else
{
pstNewHead = reverseList(head->next); // 返回新链表头节点
head->next->next = head; // 这里完成反转
head->next = NULL;
return pstNewHead;
}
}
递归写法的关键是：head->next->next = head 这句代码中，
head 是谁，head->next 是谁，head->next->next 又是谁！
可以从后往前理解，假设有三个节点，为 1 -> 2 -> 3，
最后一次：当head为节点2时，入参为传入节点3，节点3的next为NULL，返回节点3的地址。
此时： head指向节点2，pstNewHead指向节点3，
Original: https://www.cnblogs.com/payapa/p/11117454.html
Author: 努力爬呀爬
Title: leetcode的Hot100系列–206. 反转链表
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/565247/
转载文章受原作者版权保护。转载请注明原作者出处！