(4)剑指Offer之链表相关编程题
一 链表中倒数第k个节点
题目描述:
输入一个链表,输出该链表中倒数第k个结点
问题分析:
一句话概括:
两个指针一个指针p1先开始跑,指针p1跑到k-1个节点后,另一个节点p2开始跑,当p1跑到最后时,p2所指的指针就是倒数第k个节点。
思想的简单理解:
前提假设:链表的结点个数(长度)为n。
规律一:要找到倒数第k个结点,需要向前走多少步呢?比如倒数第一个结点,需要走n步,那倒数第二个结点呢?很明显是向前走了n-1步,所以可以找到规律是找到倒数第k个结点,需要向前走n-k+1步。
算法开始:
- 设两个都指向head的指针p1和p2,当p1走了k-1步的时候,停下来。p2之前一直不动。
- p1的下一步是走第k步,这个时候,p2开始一起动了。至于为什么p2这个时候动呢?看下面的分析。
- 当p1走到链表的尾部时,即p1走了n步。由于我们知道p2是在p1走了k-1步才开始动的,也就是说p1和p2永远差k-1步。所以当p1走了n步时,p2走的应该是在n-(k-1)步。即p2走了n-k+1步,此时巧妙的是p2正好指向的是规律一的倒数第k个结点处。
这样是不是很好理解了呢?
考察内容:
链表+代码的鲁棒性
示例代码:
/* //链表类 public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ //时间复杂度O(n),一次遍历即可 public class Solution { public ListNode FindKthToTail(ListNode head,int k) { ListNode pre=null,p=null; //两个指针都指向头结点 p=head; pre=head; //记录k值 int a=k; //记录节点的个数 int count=0; //p指针先跑,并且记录节点数,当p指针跑了k-1个节点后,pre指针开始跑, //当p指针跑到最后时,pre所指指针就是倒数第k个节点 while(p!=null){ p=p.next; count++; if(k<1){ pre=pre.next; } k--; } //如果节点个数小于所求的倒数第k个节点,则返回空 if(count<a) return null; return pre; } }
二 反转链表
题目描述:
输入一个链表,反转链表后,输出链表的所有元素。
问题分析:
链表的很常规的一道题,这一道题思路不算难,但自己实现起来真的可能会感觉无从下手,我是参考了别人的代码。
思路就是我们根据链表的特点,前一个节点指向下一个节点的特点,把后面的节点移到前面来。
就比如下图:我们把1节点和2节点互换位置,然后再将3节点指向2节点,4节点指向3节点,这样以来下面的链表就被反转了。
考察内容:
链表+代码的鲁棒性
示例代码:
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { ListNode next = null; ListNode pre = null; while (head != null) { //保存要反转到头来的那个节点 next = head.next; //要反转的那个节点指向已经反转的上一个节点 head.next = pre; //上一个已经反转到头部的节点 pre = head; //一直向链表尾走 head = next; } return pre; } }
三 合并两个排序的链表
题目描述:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
问题分析:
我们可以这样分析:
- 假设我们有两个链表 A,B;
- A的头节点A1的值与B的头结点B1的值比较,假设A1小,则A1为头节点;
- A2再和B1比较,假设B1小,则,A1指向B1;
- A2再和B2比较。。。。。。。
就这样循环往复就行了,应该还算好理解。
考察内容:
链表+代码的鲁棒性
示例代码:
非递归版本:
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //list1为空,直接返回list2 if(list1 == null){ return list2; } //list2为空,直接返回list1 if(list2 == null){ return list1; } ListNode mergeHead = null; ListNode current = null; //当list1和list2不为空时 while(list1!=null && list2!=null){ //取较小值作头结点 if(list1.val <= list2.val){ if(mergeHead == null){ mergeHead = current = list1; }else{ current.next = list1; //current节点保存list1节点的值因为下一次还要用 current = list1; } //list1指向下一个节点 list1 = list1.next; }else{ if(mergeHead == null){ mergeHead = current = list2; }else{ current.next = list2; //current节点保存list2节点的值因为下一次还要用 current = list2; } //list2指向下一个节点 list2 = list2.next; } } if(list1 == null){ current.next = list2; }else{ current.next = list1; } return mergeHead; } }
递归版本:
public ListNode Merge(ListNode list1,ListNode list2) { if(list1 == null){ return list2; } if(list2 == null){ return list1; } if(list1.val <= list2.val){ list1.next = Merge(list1.next, list2); return list1; }else{ list2.next = Merge(list1, list2.next); return list2; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
(3)剑指Offer之数值的整数次方和调整数组元素顺序
一 数值的整数次方 题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 问题解析: 这道题算是比较麻烦和难一点的一个了。我这里采用的是二分幂思想,当然也可以采用快速幂。更具剑指offer书中细节,该题的解题思路如下:1.当底数为0且指数<0时,会出现对0求倒数的情况,需进行错误处理,设置一个全局变量;2.判断底数是否等于0,由于base为double型,所以不能直接用==判断3.优化求幂函数(二分幂)。当n为偶数,a^n =(a^n/2)*(a^n/2);当n为奇数,a^n = a^[(n-1)/2] a^[(n-1)/2] a。时间复杂度O(logn) 时间复杂度:O(logn) 示例代码: public class Solution { boolean invalidInput=false; public double Power(double base, int exponent) { //如果底数等于0并且指数小于0 //由于base为double型,不能直接用==判断 if(equal(base,0...
- 下一篇
《Effective Java》学习笔记 第二章 创建和销毁对象
第二章 创建和销毁对象 何时以及如何创建对象,何时以及如何避免创建对象,如何确保他们能够适时地销毁,以及如何管理对象销毁之前必须进行的各种清理动作。 1.考虑用静态工厂方法代替构造器 一般在某处获取一个类的实例最常用的方法是提供一个共有的构造器,还有一种方法,就是提供一个共有的静态工厂(static factory method),他只是一个返回类的实例的静态方法。 例: public static Boolean valueOf(boolean b){ return b ? Boolean.TRUE:Boolean.FALSE; } 注意,静态工厂方法与设计模式中的工厂方法模式不同。类可以通过静态工厂方法来提供给它的客户端,而不是通过构造器,提供静态工厂方法而不是公有的构造器,这样做具有几大优势: 优势 静态工厂方法,它们有名称 例如构造器BIgInteger(int,int,Random)返回的BigInteter可能为素数,如果用名为BigInteger.probablePrime的静态工厂方法来表示,显然更为清楚。 不必在每次调用它们的时候都创建一个新的对象 这使得不可变类可以...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS6,CentOS7官方镜像安装Oracle11G
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- 设置Eclipse缩进为4个空格,增强代码规范
- Mario游戏-低调大师作品
- MySQL8.0.19开启GTID主从同步CentOS8
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果