题解 | #每K个一组反转（C++）#

/*
描述
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

说明：

1. 你需要自行定义链表结构，将输入的数据保存到你的链表中；
2. 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；
3. 你的算法只能使用常数的额外空间。
   输入描述：
   第一行输入是链表的值
   第二行输入是K的值，K是大于或等于1的整数

输入形式为：
1 2 3 4 5
2
输出描述：
当 k = 2 时，应当输出:
2 1 4 3 5

当 k = 3 时，应当输出:
3 2 1 4 5

当k=6时，应当输出：
1 2 3 4 5

Main idea:
函数式编程，将每个需要的功能（如输出，反转K个node等）抽象成函数，这样结构清晰，而且便于调试。
*/

# include<iostream>

using namespace std;

struct LinkNode {
    int value;
    LinkNode* next;
    LinkNode(int v = 0, LinkNode* l = NULL) : value(v), next(l) {}
};


void printLink(LinkNode* lHead) {
    LinkNode* out = lHead->next;
    while (out != NULL) {
        cout << out->value << " ";
        out = out->next;
    }
    cout << endl;
}


LinkNode* reverse_K_Node(LinkNode* pLeft, LinkNode* pRight) {
    // complete the task of reverse K node, and return the head of reversed link
    LinkNode* pNext = pLeft->next;
    LinkNode* tmp;
    while (pLeft!=pRight)
    {
        tmp = pNext->next;
        pNext->next = pLeft;
        pLeft = pNext;
        pNext = tmp;
    }
    return pRight;
}


LinkNode* reverseLink_K(LinkNode* lHead, int k, int length) {
    if (lHead == NULL || lHead->next == NULL) return NULL;
    if (lHead->next->next == NULL) return lHead->next;
    int count = length / k;
    LinkNode* pPrev = lHead, * pLeft, * pRight, * pNext;
    for (int i = 0; i < count; ++i) {
        pLeft = pPrev->next;
        pRight = pLeft;
        for (int j = 0; j < k - 1; j++)
            pRight = pRight->next;
        pNext = pRight->next;
        pPrev->next = reverse_K_Node(pLeft, pRight);
        for (int j = 0; j < k; j++)
            pPrev = pPrev->next;
        pPrev->next = pNext;
    }
    return lHead;

}


int main() {
    int a = 0, k = 0, n=0;
    LinkNode* link_data = new LinkNode();
    LinkNode* tmp = NULL;
    LinkNode* tail = link_data;
    LinkNode* result = NULL;
    while (true) {
        cin >> a;
        tmp = new LinkNode(a);
        tail->next = tmp;
        tail = tail->next;
        n += 1;
        if (cin.get() == '\n')
            break;
    }
    //cout << "Original Link:";
    //printLink(link_data);
    cin >> k;
    result = reverseLink_K(link_data, k, n);
    //cout << "K-reversed Link:";
    printLink(result);

    return 0;
}