链表中的节点每k个一组翻转

Introduction

Question：链表中的节点每k个一组翻转

Analysis

一般这种链表题，都在前面加入一个头结点来简化一些算法的实现，所以对于1 -> 2 -> 3 -> 4 -> 5，我们加入一个头结点得到：0 -> 1 -> 2 -> 3 -> 4 -> 5。

然后我们一边向前遍历链表，一边翻转链表，直到遇到空指针或者计数达到K。如果计数达到K，我们就已经完成了一组翻转，完成先将其与原来链表链接起来，然后再向前移动 k 步。这时相当于我们再完成一个原问题的子问题就能解决了。当然还有一个点要考虑，就是当计数达到k之前遇到空指针，我们需要将之前链表的末尾再翻转一次。

Implement

pair<ListNode*, int> reverseK(ListNode* head, int k) {
    int i;
    ListNode *pre = nullptr, *temp;
    ListNode *cur = head;
    for(i = 0;i < k && cur;i++) {
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    head->next = cur;
    return make_pair(pre, i);
}
ListNode* reverseKGroup(ListNode* head, int k) {
    // write code here
    ListNode node(0);
    ListNode *p = &node;
    p->next = head;
    while(p->next) {
        auto res = reverseK(p->next, k);
        if (res.second != k) {
            p = res.first;
            reverseK(res.first, res.second);
        } else {
            swap(p->next, res.first);
            p = res.first;
        }
    }

    return node.next;
}