链表翻转,写法和交换类似,但是需要pre cur 还有一个临时变量nxt记录下一个结点

本文主要是介绍链表翻转,写法和交换类似,但是需要pre cur 还有一个临时变量nxt记录下一个结点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归反转单链表(头插法反转部分链表

要弄pre cur 还有nxt(临时变量保存下一个结点

P0指到需要修改的链表的前一个结点

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy=new ListNode(-1,head);ListNode p0=dummy;//指向需要倒转链表的前一个for(int i=0;i<left-1;i++){p0=p0.next;}ListNode pre=null,cur=p0.next;for(int i=0;i<right-left+1;i++){ListNode nxt=cur.next;cur.next=pre;pre=cur;cur=nxt;}p0.next.next=cur;p0.next=pre;return dummy.next;}
}

K个一组的链表翻转,

在之前的基础上有所变化,先计算链表的长度。

如果长度不够则不翻转

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy=new ListNode(-1,head);ListNode p0=dummy;ListNode lenp=head;//用于计算链表长度ListNode cur=head,pre=null;int len=0;while(lenp!=null){len++;lenp=lenp.next;}while(len>=k){len-=k;for(int i=0;i<k;i++){ListNode nxt=cur.next;cur.next=pre;pre=cur;cur=nxt;}ListNode temp=p0.next;p0.next.next=cur;p0.next=pre;p0=temp;}return dummy.next;}}

如何判断回文链表

寻找回文串的核心思想是从中心向两端扩展

判断一个字符串是不是回文串就简单很多,不需要考虑奇偶情况,只需要双指针技巧,从两端向中间逼近即可:

1用递归

用快慢指针先找到链表的中间值,再反转中间值后面的链表进行比较。

class Solution {ListNode left;public boolean isPalindrome(ListNode head) {left=head;return travers(head);}boolean travers(ListNode right){if(right==null) return true;boolean res=travers(right.next);res=res&&(right.val==left.val);left=left.next;return res;}
}
class Solution {public boolean isPalindrome(ListNode head) {ListNode slow=head,fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}if(fast!=null) slow=slow.next;//奇数链表,slow往前走一步slow=reverse(slow);//翻转后要更新ListNode p1=head,p2=slow;while(p2!=null&&p1.val==p2.val){p1=p1.next;p2=p2.next;}return p2==null;}ListNode reverse(ListNode slow){ListNode pre=null,cur=slow;while(cur!=null){ListNode temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;//返回到翻转后的头结点}
}

这篇关于链表翻转,写法和交换类似,但是需要pre cur 还有一个临时变量nxt记录下一个结点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1045619

相关文章

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

变量与命名

引言         在前两个课时中,我们已经了解了 Python 程序的基本结构,学习了如何正确地使用缩进来组织代码,并且知道了注释的重要性。现在我们将进一步深入到 Python 编程的核心——变量与命名。变量是我们存储数据的主要方式,而合理的命名则有助于提高代码的可读性和可维护性。 变量的概念与使用         在 Python 中,变量是一种用来存储数据值的标识符。创建变量很简单,

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点