算法系列：链表反转问题

本文集中写链表的反转问题，因为其他的链表相交、链表数量等问题比较简单，即使没啥算法经验也能写个差不多，而链表反转也算一种经典的递归问题。这个文章的文字描述太乱了，有时间回来补图。

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。反转链表有两种实现方式，一种是迭代式实现，一种是通过递归实现。先来看通过迭代实现：迭代的反转需要使用三个指针，pre，cur 和 nxt，核心思想就是 cur 不断的向后移动过程中，让 cur 指向 pre。而这一过程分为四步：

nxt = nxt->next，先让 nxt 向后移动，因为 cur 指向 pre 之后，需要通过 nxt 找到下一个节点
cur->next = pre，实现指针的反转，让 cur 指向上一个指针
pre = cur，为下一次反转做准备，pre 就是在反转中要被指向的节点
cur = nxt，cur 指向下一个节点，为下一次反转做准备

通过以上四点，我们可以在推出一些细节：

pre 的初始值应该是 null，因为任何一个链表的末尾节点应该是空节点，而第一次反转时 cur 指向了 pre，因此 pre 也就是链表的末尾，因此 pre 初始为空
cur 的初始值就是 head 节点，nxt 的初始值也是 head 节点，因为这样才能让 nxt = nxt->next 和 cur->next = pre 有意义
如果 nxt 指向 null，说明此时链表反转完毕，而 cur 指向的就是 nxt，因此最后要返回 pre 指针

class ListNode {
public:
    int val;
    ListNode* next = nullptr;
    ListNode() = default;
    ListNode(int x) : val{x} {};
};

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

至于递归方法就简单了很多：

如果这个节点是原链表的尾部节点，那么直接将其返回，而且每一层递归函数的返回值都是它。而尾部节点的判断方式就是 head->next == null。因此先写出部分程序：如下的程序中，任何一个递归函数返回的都是链表的尾部节点。

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

在找到尾部节点后，将其余节点依次反转即可。而且一定是在找到尾部节点后反转，如果在找到尾部节点之前就反转，链表就无法向下递归。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 模板
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* last = reverseList(head->next);
        head->next->next = head; // 后面的节点指向自己
        head->next = nullptr; // 自己的下一个节点是 nullptr
        return last;
    }
};

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

我决定以后用递归了，如果用迭代去写，涉及的变量和程序都比较繁琐。基于上面的递归反转：和反转全部链表不同，部分反转链表，需要在反转后，将链表的尾部指向原链表不反转部分的下一个元素。之前指向的是 nullptr，那么这里就需要指向原链表不反转部分的第一个元素。并返回反转链表后的第一个节点。

class Solution {
public:
    ListNode* p = nullptr;
    ListNode* reverse(ListNode* node, int right) {
        // right=1 的时候，下一个元素就是不需要反转的链表的第一个元素
        if (right == 1) {
            p = node->next;
            return node;
        }
        ListNode* last = reverse(node->next, right - 1);
        node->next->next = node;
        // 之前指向 nullptr，现在指向 p
        node->next = p;
        return last;
    }

    // 返回的是链表的头部
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 反转前 k 个链表
        if (left == 1) {
            return reverse(head, right);
        }
        // 递归，head->next 移动一次，left 和 right 都递减
        // head->next 指向链表的第一个元素，无论反转或不反转，也是递归的精髓
        head->next = reverseBetween(head->next, left-1, right-1);
        return head;
    }
};

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

和上一题一样，反转后的链表末尾元素需要指向不需要反转的链表的第一个元素。第一题，反转链表的末尾元素指向 nullptr，所以需要和 nullptr 判断关系，这里同理，只是不是 nullptr 了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* reverse(ListNode* p1, ListNode* p2) {
        // 指向谁，就和谁判断，第一题的 nullptr 也是如此
        if (p1 == p2 || p1->next == p2) {
            return p1;
        }
        ListNode* last = reverse(p1->next, p2);
        p1->next->next = p1;
        p1->next = p2;
        return last;
    }

    // 返回的是反转链表的头
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr)
            return nullptr;
        ListNode* p1 = head;
        ListNode* p2 = head;
        // 如果不够反转，就不用反转
        for (int i = 0; i < k; i++) {
            if (p2 == nullptr)
                return head;
            p2 = p2->next;
        }
        // 第一次链表反转，的第一个元素一定是最后链表的头，因此要返回
        ListNode* last = reverse(p1, p2);
        // 头指针变成局部链表的尾指针，串起整个链表
        head->next = reverseKGroup(p2, k);
        return last;
    }
};