当前位置: 首页 > article >正文

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

LeetCode 热题 100_K 个一组翻转链表(31_25)

    • 题目描述:
    • 输入输出样例:
    • 题解:
      • 解题思路:
        • 思路一(四指针法):
      • 代码实现
        • 代码实现(思路一(四指针法)):

题目描述:

给你链表的头节点 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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)


http://www.kler.cn/a/442095.html

相关文章:

  • 如何通过 Apache Airflow 将数据导入 Elasticsearch
  • LLM大语言模型的分类
  • Linux使用SSH连接GitHub指南
  • 某国际大型超市电商销售数据分析和可视化
  • 每打开一个chrome页面都会【自动打开F12开发者模式】,原因是 使用HBuilderX会影响谷歌浏览器的浏览模式
  • 代码随想录 字符串 test5
  • LSTM长短期记忆网络
  • QNX系统和android系统文件互拷贝
  • 《两道有趣的编程题解析与解法》
  • Spring 不推荐使用@Autowired
  • LeetCode5. 最长回文子串(2024冬季每日一题 35)
  • 在微服务架构中,处理日志的中间件和工具非常重要,它们帮助开发者收集、存储、分析和监控日志数据。一些常用的日志处理中间件及其特点、优缺点介绍。
  • 计算机网络信息系统安全问题及解决策略
  • 在优化算法中常见哪些数学函数(根据数学性质分类)
  • 用python实现滑雪小游戏,附源码
  • CSS 核心属性详解
  • 联邦学习:披着隐私外衣的“纸老虎“?
  • docker搭建Redis集群及哨兵(windows10环境,OSS Cluster)
  • 预处理内容
  • SafeRPlan: 用于椎弓根螺钉置入术中规划的安全深度强化学习|文献速递-生成式模型与transformer在医学影像中的应用
  • lettuce 默认情况下连接池不生效,源码分析
  • 阿尔茨海默症数据集,使用yolo,voc,coco格式对2013张原始图片进行标注,可识别轻微,中等和正常的症状
  • 小程序快速实现大模型聊天机器人
  • linux oracle proc 编译报错
  • 跟沐神学读论文-论文阅读管理
  • 决策引擎技术