HOT100-10-反转链表

题目描述

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

示例 1：

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

具体见题目详解。

算法思路

这是很常见的模版题，多使用几个指针指来指去（bushi）就可以了，差不多可以看这个图片，我比较懒，就直接借鉴大佬的博客了：

这相当于是一种迭代解题思路，代码如下：

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

结果如下：

接下来我们想一个递归的思路，既然是递归，那么势必上需要将问题划分为一层一层的子问题，我们可以这样想，如果我们想让A->B->C->D->E倒过来，那我们倒数第二次得到的链表可以是这样的：A->B<-C<-D<-E，同理：

• 倒数第三次: A->B->C<-D<-E
• 倒数第四次：A->B->C->D<-E

由此我见，我们可以使用递归移动到链表的末尾，从末尾开始处理，让其指向倒数第二个节点，再返回上一层，让倒数第二个节点指向倒数第三个节点，依次处理即可，代码如下：

class Solution {
    void dg(ListNode *head) {
        if (head->next == nullptr) {
            ans = head;
            return;
        }
        dg(head->next);
        head->next->next = head;
        head->next = nullptr;
    }
public:
    ListNode * ans;
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        ListNode * last = head;
        dg(last);
        return ans;
    }
};

这里我们使用变量ans是为了方便储存最后一个节点，也就是反转后的头节点。结果如下：