[数据结构与算法]反转链表 C++ 迭代 递归

反转链表

LeeCode206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法一：迭代

prev指向前一个节点，初始化为nullptr，使链表第一个节点指向nullptr。cur指向当前正在遍历的节点，每次都使cur->next指向prev，然后prev指向cur。在此之前，要保存cur->next，用tmp保存，最后，cur指向tmp。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (nullptr != cur) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
};

解法二：递归

递归第一次返回的是反转链表后的头节点reverseHead，因此要保存，此后，递归返回的节点也是它。递归是带有状态的循环，前面的节点是指向后面的节点的，因此，使后面的节点指向前面的节点后，前面不再指向它，而是与之断开连接。

//写法一
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (nullptr == head || nullptr == head->next)
            return head;
        //反转后的头节点
        ListNode* reverseHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return reverseHead;
    }
};

个人觉得写法二比较好理解。先保存当前节点的下一个节点ListNode* tmp = cur->next;，然后当前节点指向前面一个节点cur->next = prev，最后，当前节点cur作为前一个节点prev的参数，tmp作为当前节点cur的参数(reverse(ListNode* prev, ListNode* cur))作递归。

//写法二
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }
    ListNode* reverse(ListNode* prev, ListNode* cur) {
        if (cur == nullptr)
            return prev;
        ListNode* tmp = cur->next;
        cur->next = prev;
        return reverse(cur, tmp);
    }
};