反转链表--两种思路

0x01.问题

反转一个单链表。
输入示例： 1->2->3->4->5->NULL
输出示例： 5->4->3->2->1->NULL

C++结构体：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++函数形式：  ListNode* reverseList(ListNode* head)

0x02.详细分析

当然你不可能每次去遍历尾端的一个元素然后加入新的链表，因为时间复杂度达到了O（N！)，而且额外使用了很多空间，有没有简便一点的办法呢？

我们的想法是：如果可以从尾部开始构造一个链表就好了，那么我们只需要每次拿出它的下一个元素，并指向之前的元素就好了。

这种想法是完全可行的，单链表不就是神奇在指向嘛，我们可以根据它的指向给它随意变换。

我们来看一个例子：

要想从尾部开始构建一个链表，先要保存它的下一个指向，假设为next。然后断开1的指向，指向它的前面一个，我们假设是pre，当然，初始状况下pre是空的。假设当前的节点是curr。

我们对它进行第一次操作：

这里进行了第一次操作，实际上这个节点1已经是链表的尾部了。
我们还需要更新pre和curr，pre现在应该是curr了，而curr应该是之前保留的下一个元素。

现在我们进行第二次操作：
现在进行第三次操作：

这样我们就完成了整个链表的逆转，我们整理一下思路：

• 初始化一个pre保存当前操作节点的前面一个节点。初始为NULL。
• 使用一个指针来保存它的下一个节点next。
• 断开当前操作节点的指向，使它指向pre。
• 更新pre为当前操作节点。
• 更新curr为之前保存的next。

这样我们就可以用迭代的方式很快的完成整个链表的反转。

其实，理解了上述的原理后，我们也可以使用递归的方式去解决。

这个思路就是，一直递归到尾部，然后用它做头部，然后改变它前面一个指针的->next->next为自己，也就是完成了一个节点的逆序相接，这样的递归要点是：

• 每次完成一个节点的相接。
• 返回的是已经完成逆转的链表。
• 如果遇到最后一个节点后空节点就返回。
• 核心代码是head->next->next=head head->next=NULL 也就是完成了两个节点的逆转。

如果实在还不理解，可以试着画一下执行流程，很好理解，核心是指针间指向的变化。

0x03.解决代码–迭代

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

时间复杂度：O（N）
空间复杂度：O（1）

0x04.解决代码–递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode*p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }
};

时间复杂度：O（N）
空间复杂度：O（N） 递归导致的栈空间消耗

ATFWUS --Writing By 2020–03–24