k个一组翻转链表

问题描述

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

输入输出样例

Input: [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

  由于长度为2，所以我们仅需对前4个节点进行操作。对于最后一个节点保持原样。

题解

  对于这道题目，我们对其进行逐步分析。首先对于链表这个数据结构来说，它本身就是一个兼具递归与迭代性质的数据结构。认真分析一下，就可以发现这个问题也是具有递归性质的。

  那么什么是递归性质呢？ 举个例子，我们对于链表调用reverseKGroup(head, 2)。即以两个节点为一组的反转链表。那么对于这两个处理好后，我们就需要对这个链表的后续结点接着操作，这些也就是子问题。

  利用递归性质，我们可以推导出如下算法：1、先翻转head为头的k个元素；2、将第k+1个元素作为head递归调用reverseGroup函数。3、最后将它们拼接起来，就可以形成最终的代码了。

具体代码实现如下所示

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseN(ListNode* a,ListNode* b) {
        ListNode* prev = nullptr;
        ListNode* cur = a;

        while (cur != b) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr) return nullptr;
        ListNode* a = head;
        ListNode* b = head;

        for (int i = 0;i < k; i++) {
            if (b == nullptr) return head;
            b = b->next;
        }
        ListNode* res = reverseN(a,b);
        a->next = reverseKGroup(b,k);
        return res;
    }
};