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

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

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

示例

解题思想







代码

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* reverse(ListNode* head) {
		ListNode* curr, * prev;
		curr = head, prev = nullptr;
		while (curr) {
			ListNode* next = curr->next;
			curr->next = prev;
			prev = curr;
			curr = next;
		}
		return prev;
	}

	ListNode* reverseKGroup(ListNode* head, int k) {
		ListNode* dummy = new ListNode(0);
		dummy->next = head;
		ListNode* start, * end;
		start = dummy, end = dummy;

		while (true) {
			for (int i = 0; i < k && end; i++) end = end->next;
			if (!end) break;

			ListNode* endNext = end->next;
			ListNode* startNext = start->next; //记录的是开始的头节点，反转后的尾节点

			end->next = nullptr;
			
			start->next = reverse(start->next); 
			startNext->next = endNext; //连接反转后的尾节点和下一阶段的头节点

			start = end = startNext;
		}
		return dummy->next;
	}
};