反转链表 -> 反转链表 II-> K 个一组翻转链表

从翻转一个单链表，到指定部分反转，再到K个一组的一组一组反转，渐进式的增加难度。

反转链表

对于链表的反转，其实类似于数组的逆序，数组的逆序很简单，使用前后碰撞指针就可以了。

而链表由于其特殊性，需要对于指针进行操作，对于a->b->c->d这一链表，我们想要的结果就是a<-b<-c<-d，针对到每个节点，我们只需让其的next指针指向上一个节点，那么我们在这里就需要使用前后快慢指针记录前后节点。

当实际操作时会发现，对于a节点，它是没有前一个节点的，同时反转后它的next应该是NULL，所以慢指针应该初始化为NULL，快指针初始化为head。

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode():val(0),next(nullptr){}
    ListNode(int v): val(v),next(nullptr){}
    void print() {
        ListNode* p = this;
        while(p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
};

ListNode* reverse(ListNode* cur) {
    ListNode* last = nullptr;
    ListNode* fast = cur;
    while(fast) {
        ListNode* tmp = fast->next;
        fast->next = last;
        last = fast;
        fast = tmp;
    }
    return last;
}

int main() {
    ListNode* head = new ListNode();
    ListNode* p = head;
    int n;
    cin >> n;
    while(n --) {
        int v;
        cin >> v;
        p->next = new ListNode(v);
        p = p->next;
    }
    head = head->next;
    head->print();
    reverse(head)->print();
}

反转链表Ⅱ

反转链表Ⅱ相较于反转链表，就是多了一个区域限制。

我们可以首先将指针移动到指定起始地点，但我们还不能直接reverse，因为这样会使得后面所有的节点都被反转，所以我们需要计算反转的个数，按个数反转

那么在其中就要涉及到三个指针

• pre，指向的是待反转区域的上一个节点
• last：反转之前指向NULL，反转之后是反转区域的头节点
• fast：反转之前是反转区域的头节点，反转之后是反转区域的下一个节点

假设有一个链表为 1->2->3->4->5 ，我们需要对234区域反转，那么刚反转后的中间状态如下：

                  l f
      null<-2<-3<-4 5->null
            ^
            |
            1
            p

和上文描述的一致。

接着，我们需要将现在的三个链表连在一起。

我们先看第一段1和第二段234的连接。根据结果知道，1后面应该连接的是4，所以我们应该pre->next = last。

再看第二段234和第三段5->null的连接，应该将5连在2的后面，所以就是pre->next->next = fast。但是注意，这时的pre->next已经被上一个操作改变，所以我们需要将两次操作调换位置，先连接第二段和第三段。

结果就是1->4->3->2->5。

最后还有一种特殊情况需要处理，当我们的区域从第一个开始时，我们会没有pre，所以需要建立一个虚拟空结点。

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr){}
    ListNode(int v): val(v), next(nullptr){}
    void print() {
        ListNode* p = this;
        while(p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
};

int main() {
    int n;
    cin >> n;
    ListNode* head = new ListNode();
    ListNode* p = head;
    while(n --) {
        int v;
        cin >> v;
        p->next = new ListNode(v);
        p = p->next;
    }
    int left, right;
    cin >> left >> right;
    ListNode* pre = head;
    for(int i = 0; i < left - 1; i ++) pre = pre->next;
    ListNode* fast = pre->next;
    ListNode* last = nullptr;
    for(int i = 0; i < right - left + 1; i ++) {
        ListNode* tmp = fast->next;
        fast->next = last;
        last = fast;
        fast = tmp;
    }
    pre->next->next = fast;
    pre->next = last;
    head->next->print();
    return 0;
}
// 输入
// 5
// 1 2 3 4 5
// 2 4
// 输出
// 1 4 3 2 5

K个一组反转链表

这道题目相较于第二道更进一步，划分区域k，从头开始一组一组反转，最后不足的不需要反转。

这道题我们可以使用一个不同的方法，在第二题中，我们是按照个数来反转链表，我们在这到题中可以设置一个end指针，将其遍历到当前需要处理的区间尾部，断开当前区间和后面的链表的连接，这样我们就可以直接复用反转链表的代码了。

注意这里也需要虚拟头节点，在初始化时就已经定义好了。

#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
    ListNode* next;
    int val;
    ListNode(int val = 0): val(val), next(nullptr){}
    void print() {
        ListNode* p = this;
        while(p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
};
ListNode* reverse(ListNode* head) {
    ListNode* fast = head;
    ListNode* last = nullptr;
    while(fast) {
        ListNode* tmp = fast->next;
        fast->next = last;
        last = fast;
        fast = tmp;
    }
    return last;
}
//   p s e n
// 1 2 3 4 5
void work(ListNode* head, int k) {
    ListNode* pre = head;
    ListNode* end = head;
    while (end->next) {
        for(int i = 0;i < k && end; i ++) end = end->next;
        if(end == nullptr) break;
        ListNode* start = pre->next;
        ListNode* nxt = end->next;
        end->next = nullptr;
        pre->next = reverse(start);
        start->next = nxt;
        pre = start;
        end = start;
    }
    head->next->print();
}

int main() {
    int n;
    cin >> n;
    ListNode* head = new ListNode();
    ListNode* p = head;
    while(n --) {
        int v;
        cin >> v;
        p->next = new ListNode(v);
        p = p->next;
    }
    int k;
    cin >> k;
    work(head,k);
    return 0;
}