25K个一组翻转链表（单链表操作）

1、题目描述

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

2、示例

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

3、题解

方法一：

单链表操作

• 对链表head不断进行K组翻转，翻转后的保存在新链表start中
• cur指向head链表中当前一组K链表的头，q往后移K个指向下一组K链表的头
• q往后移K个过程中，如果下一组没有K个直接返回p->next=cur，不需要翻转
• p指向已经翻转的start链表的尾部，通过头插法对当前一组K链表进行翻转
• 最后p继续指向尾部，cur继续指向下一组要翻转的K链表头部也就是q

方法二：

使用栈，实现k个节点的翻转

• 从链表头开始扫描，temp指向翻转的k个节点的头节点
• 将翻转的k个节点入栈，如果节点总数不是k的整数倍，将最后剩余的节点保持原有顺序，不用翻转直接返回结果
• 将翻转的k个节点出栈，连接到temp节点后面，实现了k个节点翻转
• temp指向下一个翻转的k个节点的头节点

#include<iostream>
#include<vector>
using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
};
class Solution0 {
public:
	ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *start=new ListNode(0);
    ListNode *p=nullptr,*q=nullptr,*cur=nullptr;
		cur=head;
		p=start;
		while(cur!=nullptr){
			q=cur;
			bool is_need_reverse=true;
			// cur指向当前一组K链表的头，q往后移K个指向下一组K链表的头
			for(int i=0;i<k;i++){
				if(q==nullptr){
					p->next=cur; //如果下一组没有K个直接返回，不需要翻转
					is_need_reverse=false;
					break;
				} else {
					q=q->next;
				}
			}
			if(!is_need_reverse) break;
			ListNode *tmp=cur;
			// p指向已经翻转的链表的尾部，通过头插法对当前一组K链表进行翻转
			for(int i=0;i<k;i++){
				ListNode *nextnode=cur->next;
				cur->next=p->next;
				p->next=cur;
				cur=nextnode;
			}
			// p继续指向尾部
			p=tmp;
			// cur继续指向下一组要翻转的K链表头部
			cur=q;
		}
    return start->next;
  }
};
class Solution {
public:
	ListNode* reverseKGroup(ListNode* head, int k) {
		ListNode* temp = new ListNode(0), * pre,* p;  //temp指向翻转的k个节点的头节点，pre->next存储返回的头节点，p为翻转的k个节点的头节点
		vector<ListNode*> reverseNode;  //存储翻转节点的栈
		temp->next = head;  //初始化temp，temp指向翻转的k个节点的头节点
		pre = temp;  //pre->next存储返回的头节点
		int i;
		//从链表头开始扫描
		while (temp->next != NULL)
		{
			reverseNode.clear();
			//p为翻转的k个节点的头节点
			p = temp->next;
			i = 0;
			//将翻转的k个节点入栈
			while (i < k)
			{
				reverseNode.push_back(p);
				p = p->next;
				//如果节点总数不是k的整数倍，将最后剩余的节点保持原有顺序，不用翻转直接返回结果
				if (p == NULL && i != k - 1)
					return pre->next;
				i++;
			}
			//将翻转的k个节点出栈，实现了k个节点翻转
			while (i > 0)
			{
				temp->next = reverseNode[i-1];
				temp = reverseNode[i-1];
				i--;
			}
			//temp指向下一个翻转的k个节点的头节点
			temp->next = p;
		}
		return pre->next;
	}
};
//尾插法创建链表
void CreateList(ListNode* head, int n)
{
	ListNode* p;
	for (int i = 1; i <= n; i++)
	{
		p = new ListNode(i);
		head->next = p;
		head = p;
	}
}
int main()
{
	Solution solute;
	int n = 5, k = 3;
	ListNode* head = new ListNode(0), * res;
	CreateList(head, n);
	res = solute.reverseKGroup(head->next, k);
	while (res != NULL)
	{
		cout << res->val << endl;
		res = res->next;
	}
	return 0;
}