LeetCode 热题 100_K 个一组翻转链表（31_25_困难_C++）(四指针法)

题目描述：

给你链表的头节点 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

题解：

解题思路：

思路一（四指针法）：

1、通过题目分析，在每次翻转前需要进行个数的判断，若满足再将k个结点翻转，将翻转后的答案进行连接。
我们发现我们在进行翻转的时候需要保存k个结点的首和尾（kHead和kTail），并且还需要保存kHead之前的一个结点（ansTail）和kTail之后的一个结点(next_kHead)，方便将翻转后的链表进行连接和剩余结点的处理，因此我们需要四个指针（kHead、kTail、ansTail、next_kHead）。

具体实现思路请看下图：

代码实现

代码实现（思路一（四指针法））：

//判断剩余长度是否>=k，不够则返回nullptr，够则返回k个长度链表的尾结点 
ListNode *judgeLen_k(ListNode *kHead,int k){
	while(k-1){
		if(kHead==nullptr){
			return nullptr;
		}
		kHead=kHead->next;
		--k;
	}
	return kHead; 
} 

//翻转固定个数的链表，返回翻转后的头结点 
ListNode *reverseList_k(ListNode *kHead,int k){
	ListNode *pre=nullptr,*r=kHead,*tmp=kHead;
	while(k){
		r=r->next;
		tmp->next=pre;
		pre=tmp;
		tmp=r;
		--k;
	}
	return pre;
} 

//K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {
	ListNode *dummyHead=new ListNode(0); 
	//存储答案的尾结点 
	ListNode *ansTail=dummyHead;
	//交换前,k个结点的头
	ListNode *kHead=head;
	//交换前,k个结点的末尾,不够k个则为nullptr 
	ListNode *kTail=judgeLen_k(kHead,k);
	//保存下一个区间的头
	ListNode *next_kHead=nullptr;
	while(kTail!=nullptr){
		//保存下一个区间的头
		next_kHead=kTail->next;
		//翻转k个结点
		reverseList_k(kHead,k);
		
		//将k个结点翻转后的链表，连接到答案列表 
		ansTail->next=kTail;
		kHead->next=next_kHead;
		
		//更新答案链表的尾结点
		ansTail=kHead;
		//更新交换前,k个结点的头 
		kHead=next_kHead; 
		//判断之后的结点是否够k个 
		kTail=judgeLen_k(next_kHead,k);
		
		 
	} 
	ListNode *ansHead=dummyHead->next;
	delete dummyHead;
	return ansHead;         
} 

代码调试

#include<iostream>
#include<vector>
using namespace std;

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){}
}; 

//尾插法创建单链表
ListNode *createList(vector<int> arr){
	ListNode *head=nullptr,*tail=nullptr;
	for(const auto &val:arr){
		if(head==nullptr){
			head=tail=new ListNode(val);
		}else{
			tail->next=new ListNode(val);
			tail=tail->next;
		}
	}
	return head;
} 

//判断剩余长度是否>=k，不够则返回nullptr，够则返回k个长度链表的尾结点 
ListNode *judgeLen_k(ListNode *kHead,int k){
	while(k-1){
		if(kHead==nullptr){
			return nullptr;
		}
		kHead=kHead->next;
		--k;
	}
	return kHead; 
} 

//翻转固定个数的链表，返回翻转后的头结点 
ListNode *reverseList_k(ListNode *kHead,int k){
	ListNode *pre=nullptr,*r=kHead,*tmp=kHead;
	while(k){
		r=r->next;
		tmp->next=pre;
		pre=tmp;
		tmp=r;
		--k;
	}
	return pre;
} 

//K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {
	ListNode *dummyHead=new ListNode(0); 
	//存储答案的尾结点 
	ListNode *ansTail=dummyHead;
	//交换前,k个结点的头
	ListNode *kHead=head;
	//交换前,k个结点的末尾,不够k个则为nullptr 
	ListNode *kTail=judgeLen_k(kHead,k);
	//保存下一个区间的头
	ListNode *next_kHead=nullptr;
	while(kTail!=nullptr){
		//保存下一个区间的头
		next_kHead=kTail->next;
		//翻转k个结点
		reverseList_k(kHead,k);
		
		//将k个结点翻转后的链表，连接到答案列表 
		ansTail->next=kTail;
		kHead->next=next_kHead;
		
		//更新答案链表的尾结点
		ansTail=kHead;
		//更新交换前,k个结点的头 
		kHead=next_kHead; 
		//判断之后的结点是否够k个 
		kTail=judgeLen_k(next_kHead,k);
		
		 
	} 
	ListNode *ansHead=dummyHead->next;
	delete dummyHead;
	return ansHead;         
} 

int main(){
	vector<int> a={1,2,3,4,5};
	int k=2;
	ListNode *head=createList(a);
	ListNode *test=reverseKGroup(head,k); 
	while(test!=nullptr){
		cout<<test->val<<"->";
		test=test->next;
	}
	cout<<"null"; 
	return 0;
}

反转链表(23_206_简单_C++)(单链表_迭代_递归)：有关反转链表的知识请点击此链接

LeetCode 热题 100_K 个一组翻转链表（31_25)原题链接
欢迎大家和我沟通交流(✿◠‿◠)