反转链表C/C++实现与解析_c编程实现,输入头节点指针,输出null,返回逆序后链表头

---

力扣题号206
剑指offer题号24
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、双指针法

首先定义一个cur指针，指向头节点，再定义一个pre指针，指向cur反转前的前边节点，先初始化为空指针nullptr，为了不和链表的结构体定义中的next混淆，这里需要定义一个名字叫temp的指针，指向反转前cur节点的下一个节点。
为啥要用temp保存cur原先的下一个节点呢，因为反转后，我们需要往后移反转后边的节点，cur与原先的下一个节点没有关系了，就需要用temp去存原先的下一个节点，方便cur与pre往后移动，以此能够反转后边的节点.
例如下图这样，1和2反转成功了，temp指向的3，要向后移动
就需要先执行pre = cur;
然后是cur=temp
temp=cur->next;
这样就实现了后移
我们来看C/C++代码怎么去实现的

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp;//指向当前的下一个节点
        ListNode* cur = head;//当前节点
        ListNode* pre = nullptr;//当前节点的前一个节点
        while(cur) {
            temp = cur->next;//每次反转前，temp保存cur反转前的下一个节点
            cur->next = pre;//反转操作
            pre = cur;//pre往后移
            /*
            这一步容易出错，很多同学把这里写成了cur=cur->next,
            反转后，这样的做就相当于节点往前边移动了，这是不对的
            */
            cur = temp;//cur往后移
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

然后有人问啊，为啥最后是return pre呢，因为我们看哈，最后反转的结果是，cur指向的是反转前的尾结点的下一个空指针，pre指向的是新的尾结点

最后通过

二、递归法

我们再来说说递归法
递归法呢，是在某位大佬的书上看到的，cur不断指向pre的过程，在最后cur为空时判断结束
我们来看看代码实现

class Solution {
public:
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if (cur == nullptr) { //递归跳出条件
            return pre;//返回链表的最后一个节点，新的头节点
        }
        ListNode* temp = cur->next;//保存反转前cur的下一个节点
        cur->next = pre;//反转操作
        return reverse(cur, temp);//递归操作
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);//头节点前边的空节点与头节点先反转，最后返回新的头节点
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后这种方法过了