【牛客网】BM1：翻转链表

今天打算开启新一轮刷题了，必须得刷了，再不刷就得成废物了。

也希望看我博客的老哥能监督一下我，一起进步嘛！

题目BM001

打算从牛客网的面试top101开始刷起来，今天是BM001反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n)。

解法1：循环

最简单的办法就是用指针来一个一个修改链接，每次都将当前节点的next链接为上一个节点，最终再将开头的节点（单独存一下原本的开头）的next链接为空，返回最后一个节点即可。

很常规的写法，参考注释

class Solution
{
public:
    ListNode *ReverseList(ListNode *head)
    {
        // 因为需要O(1)空间复杂度，所以我们不能用很蠢的将数据遍历出来后倒序放回的办法
        // 时间复杂度是O(N) 也要求我们写的代码相对来说效率需要高一些
        if (head == nullptr || head->next == nullptr)
        {
            return head; // 只有一个或者为空的情况下，直接跳过
        }
        ListNode *old_head = head; // 单独存头
        ListNode *A, *B, *C;       // 三个指针
        A = head;
        B = head->next;
        C = head->next->next;
        while (C != nullptr)
        {
            // B修改链接为B的前一个（A在原视链表中是B的前一个）
            B->next = A;
            A = B;       // A变成B（也相当于A在原视链表中，往后走一步）
            B = C;       // B往后走一步
            C = C->next; // C往后走一步
        }
        // 走到这里是B的下一个C已经为nullptr，代表B是最后一个节点
        B->next = A; // 依旧是链接
        old_head->next = nullptr;
        return B; // B是原视链表的最后一个节点，新链表的第一个节点
    }
};

解法2：递归

一般面试的时候，面试官更希望看到递归的办法，因为这样的代码更加简洁，思路也更加有挑战性（反正你就要往难的办法想）

递归的思路也是让下一个节点的next链接为当前节点。主要在于递归的末端条件应该是head->next==nullptr的时候就需要退出了，因为此时 head->next->next是无效的，没有办法进行链接。

整个过程大概就是下面这个简图了，其中方框代表的是节点，圆形代表每一步

上代码，这里将 head->next = NULL;是为了操作第一个节点（原视链表的首节点）的时候，将下一位改成空。而在中间节点的时候，因为当前节点的next会在上一层递归的时候被修改回去，所以设置为空不会出现问题。

ListNode *ReverseList(ListNode *head)
{
    // 特判：注意不要漏掉head->next==NULL的情况
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    // 递归调用
    ListNode *ans = ReverseList(head->next);
    // 让当前结点的下一个结点的 next 指针指向当前节点
    head->next->next = head;
    // 同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
    head->next = NULL;
    return ans;
}