Leetcode.25 K个一组翻转链表(模拟/递归）

 题目链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
 

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

思路： 先定义一个反转链表的方法，递归调用即可。注意其中指针的使用，这是易错易混点。

C++代码：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);  //创建一个哑结点
        dummy->next = head;  //哑结点指向原链表的头结点
        ListNode* pre = dummy, *end = dummy;
        while(end->next != NULL){
            for(int i = 0; i < k and end != NULL; i++) end = end->next;
            if(end == NULL) break;
            ListNode* start = pre->next; //start指向要反转的部分的第一个结点
            ListNode* next = end->next;  //起到临时结点的作用，使得更好地链接链表
            end->next = NULL;  //为了反转链表，不然reverList里的while跳不出去
            pre->next = reverseList(start);  //递归反转链表
            start->next = next; //每次反转完一部分，之前的指针也要跟上来
            pre = start; 
            end = pre;
        }
        return dummy->next;
    }

    ListNode* reverseList(ListNode* head){  //迭代法反转链表
        ListNode* cur = head, *pre = NULL;
        while(cur){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};