[数据结构与算法]链表必做题 最好理解的两种简单方法 图解 206.反转链表（c++）Leetcode 题解

题目：

???? 提示：由于CSDN不支持Leetcode将图片转化为类似ppt形式的界面，笔者推荐去LeetCode看本题解
????LeetCode题解链接：206.反转链表

????给你单链表的头节点head,请你反转链表,并返回反转后的链表。
示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]
输出：[2,1]

示例3：

输入：head = []
输出：[]

解题思路

????本文主要给算法的初学者提供思路，所以不会讲解递归的思路。
????初学者请注意：凡是涉及链表的操作，一定要在纸上画图，先把过程画下来，写程序才能顺畅，空想很容易暴毙。
方法一：头插法，建立虚拟头节点temp
????既然反转一整个链表很难，那就先反转一个节点。
????1.建立反转后的链表的虚拟头节点temp，此时head指向原链表第一个节点，temp->next指向NULL;
????2.将head->next指向temp->next，temp->next指向head节点，那么此时就完成了一个节点的反转;
????如下图所示:

????3.一个节点反转完了，其他的节点也是同样的反转方式，即

    head->next=temp->next;
    temp->next=head;

????4.为了防止由于head->next改变后找不到下一个节点，应在节点反转之前，先将head->next进行备份。

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp=new ListNode(-1);
        while(head)
        {
            ListNode* Next=head->next;
            head->next=temp->next;
            temp->next=head;
            head=Next;
        }
        return temp->next;
    }
};

方法二：迭代
????本方法相对于初学者，其实不是很好理解，不过只要把图画出来了，就好理解了。
????首先还是先反转一个节点，在推广到反转整个链表。
????1.设置反转之后新链表的头结点地址pre，由于一开始并未有节点反转，pre=NULL;
????2.设置原链表头结点cur并开始链表遍历，每遍历一个结点，如方法一一样，应该用Next指针备份cur->next；
????3.将cur->next指向pre，此时新链表的头结点pre应更新为cur，那么此时就完成了一个节点的反转；
????如下图所示：

????4.继续遍历至原链表头结点cur为空

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur=head;
        ListNode* pre=NULL;
        while(cur)
        {
            ListNode* Next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=Next;
        }
        return pre;
    }
};

算法复杂度：
????由于只进行了链表的一次遍历，时间复杂度为：O(n)，空间复杂度为：O(1)。