原始鏈表：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
k = 2：1 -> 0 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6 -> 9 -> 8 -> NULL
k = 3：2 -> 1 -> 0 -> 5 -> 4 -> 3 -> 8 -> 7 -> 6 -> 9 -> NULL

#include <iostream>
#include <stdlib.h>

using namespace std;

struct link_node {
    int i;
    link_node *next;
};

//標(biāo)準(zhǔn)鏈表翻轉(zhuǎn)
link_node * reverse(link_node * head) {
    if (head == NULL) {
        return NULL;
    }

    link_node *p = head->next;
    head->next = NULL;
    while (p != NULL) {
            link_node *q = p->next;
            p->next = head;
            head = p;
            p = q;
    }

    return head;
}

/* 更簡(jiǎn)潔
link_node * reverse(LinkNode *head)
{
        link_node *pre = NULL;

        while (head != NULL)
        {
                link_node *p = head->next;
                head->next = pre;
                pre = head;
                head = p;
        }

        return pre;
}
*/

//鏈表每k個(gè)元素翻轉(zhuǎn)
link_node *reverse_k(link_node * head, int k) {
    link_node *p = head;
    link_node *last_tail = NULL; 
    link_node *new_head = NULL;

    while (p != NULL) {
        //截取鏈表的k個(gè)元素
        link_node *q = p;
        for (int i=0; i<k-1; ++i) {
            if (q == NULL) break;
            q = q->next;
        }

        //如果沒有到鏈表尾部，用tmp記錄鏈表的剩余部分
        link_node *tmp = NULL;
        if (q != NULL) {
            tmp = q->next;
            q->next = NULL;  //將k個(gè)元素的鏈表末尾指向NULL，形成一個(gè)新鏈表，以便進(jìn)行標(biāo)準(zhǔn)鏈表翻轉(zhuǎn)
        }

        link_node *h = reverse(p);  //翻轉(zhuǎn)后，h為新鏈表頭，p為新鏈表尾

        if (p == head) new_head = h;  //第一批k個(gè)元素翻轉(zhuǎn)后的頭是最終鏈表的頭
        else last_tail->next = h;           //其余每k元素鏈表的頭接到上批k元素鏈表的尾

        last_tail = p;  //記錄上批k元素鏈表的尾
        p = tmp;        //移到鏈表剩余部分開始處理下批k
    }

    return new_head;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        cerr << "Usage: " << argv[0] << " k" << endl;
        return -1;
    }
    link_node *head = new(link_node);
    head->i = 0;
    link_node *p = head;
    for (int i=1; i<10; ++i) {
        link_node *tmp = new(link_node);
        tmp->i = i;
        p->next = tmp;
        p = p->next;
    }
    p->next = NULL;

    cout << "src link" << endl;
    p = head;
    while (p!= NULL) {
        cout << p->i << " -> ";
        p = p->next;
    }
    cout << "NULL" << endl;

    cout << "new link" << endl;
    link_node *head2 = reverse_k(head, atoi(argv[1]));
    p = head2;
    while (p!= NULL) {
        cout << p->i << " -> ";
        p = p->next;
    }
    cout << "NULL" << endl;

    return 0;
}