剑指 Offer 24. 反转链表

</br></br>

题目：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

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

限制：

0 <= 节点个数 <= 5000

</br></br>

思路一：

双指针法：可以通过改变链表中节点的next指针的指向从而实现链表的反转。

1.设置两个节点prev和cur，cur表示当前节点，prev表示当前节点的上一个节点，初始状态设置为prev = nullptr; cur = head；再设置一个结点tmp记录cur的下一个结点，即tmp = cur->next；

2.改变cur结点next指针的指向，让其指向前一个结点prev，然后再通过prev = cur; cur = tmp; tmp = cur->next更新cur节点、prev节点和tmp节点；

3.依次向后循环，当cur为空的时候，说明已经遍历完所有的节点，此时prev指向的节点就是反转后链表的头节点，返回的时候返回prev。

代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head; 
        ListNode* prev = nullptr;
        while(cur)
        {
            ListNode* tmp = cur->next; //保存cur的下一个结点
            cur->next = prev;
            prev = cur;
            cur = tmp; 
        }
        return prev;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)

</br></br>

思路二：

递归：递归法和双指针法的逻辑相同，也是通过改变指针的指向从而实现反转。

1.递归函数中当cur不为空的时候，先记录下cur节点的下一个节点，再改变cur节点的next指针使其指向prev；

2.发生递归，递归参数中的cur和tmp传到下一层函数后，cur充当prev，tmp充当cur；

3.当cur为空时递归结束，返回prev结点，此时的prev结点就是反转后的头结点；

双指针法中的循环以及pre = cur; cur = temp;通过递归实现了。

代码如下：

class Solution {
public:
    ListNode* Reverse(ListNode* prev,ListNode* cur)
    {
        if(cur == nullptr)
        {
            //当cur为空的时候，已经遍历完成，此时prev就是反转后链表的头节点 
            return prev;
        }
        ListNode* tmp = cur->next;
        cur->next = prev;//改变cur的next指针指向
        return Reverse(cur,tmp);
    }
    ListNode* reverseList(ListNode* head) {
        return Reverse(nullptr,head);
    }
};

时间复杂度：O(N)

空间复杂度：O(N)