面试算法题：
给定一个长度为 n 的整型链表，要求将链表的每 k 个元素反转，反转算法使用的内存复杂度为 O(1)（忽略输入数组中的 O(n) 内存，只是为了演示尾插法建立链表，否则完全可以不用数组保存）。

输入
n, k
a1, a2, ... , an，n 个整型数据

测试数据：

case 0:
    input:
    3 1
    1 2 3
    output:
    1 2 3

case 1:
    input:
    5 2
    1 2 3 4 5
    output:
    2 1 4 3 5

case 2:
    input:
    6 3
    1 2 3 4 5 6
    output:
    3 2 1 6 5 4 

思路是先实现递归反转单个链表，再按顺序遍历待反转的链表，每当遍历到 k 个元素时做一次子链表反转，直到链表末尾为止。

带表头节点的实现

// K 链表反转， 带头节点的版本。
#include <iostream>
#include <cstdio>
using namespace std;

struct Node {
    int data;
    Node *next;
};

void show(Node* h) {
    while(h->next != NULL) {
        // 注意偷懒没处理末尾的空格
        printf("%d ", h->next->data);
        h = h->next;
    }
    printf("\n");
}

void destroy(Node* h) {
    Node *p = h;
    Node *q;
    while(p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
}

Node* inverse(Node* h) {
    if (h->next == NULL) return h;

    Node *new_h = inverse(h->next);

    // 反转后的子链表末尾节点 next 指向 h
    h->next->next = h;

    // h next 指向为空
    h->next = NULL;

    return new_h;
}

Node* k_inverse(Node *h, int k) {
    Node *new_h = NULL; // 保存新的链表头
    Node *p = h; // 指向待反转的子链表的第一个节点
    Node *q = h; // 指向待反转的子链表的最后一个节点
    Node *prev_h = h; // 指向子链表的前一个节点
    int cnt = 0;

    while(q != NULL) {
        cnt ++;
        if (cnt % k == 0 || q->next == NULL) {
            // 反转 [p, q] 子链表
            Node *s = q->next;
            q->next = NULL;

            inverse(p);

            // 标记新的表头
            if (new_h == NULL) {
                new_h = q;
            }

            // 将当前子链连接到上一段
            if (prev_h != NULL) {
                prev_h->next = q;
            }

            prev_h = p;
            p->next = s;
            p = s;
            q = s;
            cnt = 0;

            continue;
        }

        q = q->next;
    }

    return new_h;
}

int main() {
    int n, k;
    while(scanf("%d%d", &n, &k) != EOF) {
        Node *L = (Node*) malloc(sizeof(Node));
        Node *tail = L;

        while(n --) {
            int d;
            scanf("%d", &d);

            Node *p = (Node*) malloc(sizeof(Node));
            p->data = d;
            p->next = NULL;

            tail->next = p;
            tail = p;
        }

        // inverse all node except head node(empty node).
        Node *new_h = k_inverse(L->next, k);
        L->next = new_h;
        show(L);

        destroy(L);
    }

    return 0;
}

不带表头节点的实现

不带头节点的链表实现方式，相比带头节点的实现稍微复杂一些（包括建立链表等）感受下：

// K 链表反转，不带头节点的版本。
#include <iostream>
#include <cstdio>
using namespace std;

struct Node {
    int data;
    Node *next;
};

// 头插法建链表
Node* init_list_headinsert(int a[], int n) {
    Node *h = NULL;

    for (int i = 0 ; i < n; i ++) {
        Node *p = (Node*) malloc(sizeof(Node));
        p->data = a[i];
        p->next = NULL;

        if (h == NULL) {
            h = p;
            continue;
        }

        p->next = h;
        h = p;
    }

    return h;
}

// 尾插法建链表
Node* init_list_tailinsert(int a[], int n) {
    Node *h = NULL;
    Node *tail = h;

    for (int i = 0 ; i < n; i ++) {
        Node *p = (Node*) malloc(sizeof(Node));
        p->data = a[i];
        p->next = NULL;

        if (h == NULL) {
            h = p;
            tail = h;
            continue;
        }

        tail->next = p;
        tail = p;
    }

    return h;
}

// 递归反转单链表
Node* inverse(Node *h) {
    if (h->next == NULL) {
        return h;
    }

    Node *p = h->next;
    Node *new_h = inverse(h->next);
    p->next = h;
    h->next = NULL;

    return new_h;
}

// inverse every k element in list.
Node* k_inverse(Node *h, int k) {
    Node *new_h = NULL; // 返回的新链表表头
    Node *p = h, *q = h; // p 指向待反转链表的开始节点，q 指向待反转链表的末尾节点
    Node *prev_h = NULL; // prev_h 指向待反转子链表的前一个节点
    int cnt = 0;
    while(q != NULL) {
        cnt ++;
        if (cnt % k == 0 || q->next == NULL) {
            // inverse sub list [p, q]
            Node *s = q->next;
            q->next = NULL;

            inverse(p);
            p->next = s;

            if (new_h == NULL) {
                new_h = q;
            }

            if (prev_h != NULL) {
                prev_h->next = q;
            }

            prev_h = p;
            p = p->next;
            q = p;

            cnt = 0;

            continue;
        }

        q = q->next;
    }

    return new_h;
}

void show(Node* h) {
    while(h != NULL) {
        printf("%d ", h->data);
        h = h->next;
    }

    printf("\n");
}

void destroy(Node* h) {
    Node *p = h;
    Node *q;
    while(p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
}

int main() {
    int n, k;
    Node *h = NULL;
    while(scanf("%d%d", &n, &k) != EOF) {
        int *a = new int[n];

        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }

        // Node* L1 = init_list_headinsert(a, n);
        Node* L2 = init_list_tailinsert(a, n);
        // show(L1);
        // show(L2);

        Node* L3 = k_inverse(L2, k);
        show(L3);

        // destroy(L1);
        destroy(L2);
         delete []a;
    }

    return 0;
}