文档章节

剑指offer题目系列三(链表相关题目)

o
 osc_z1hvg4cu
发布于 2018/04/24 20:21
字数 1423
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

        本篇延续上一篇剑指offer题目系列二,介绍《剑指offer》第二版中的四个题目:O(1)时间内删除链表结点、链表中倒数第k个结点、反转链表、合并两个排序的链表。同样,这些题目并非严格按照书中的顺序展示的,而是按自己学习的顺序,每个题目包含了分析和代码。

        9、O(1)时间内删除链表结点

        题目:

        在O(1)时间内删除链表结点。给定单链表的头指针和一个结点指针,定义一个方法在O(1)时间内删除该结点。

        单链表的定义如下:

     

        解答:

        单向链表删除一个结点,最直观的想法是从链表的头结点开始顺序遍历查找要删除的结点,然后删除该结点,这种做法的时间复杂度为O(n),显然不满足本题要求。如果我们把下一个结点的信息复制到要删除的结点上,覆盖原有内容,再把下一个结点删除,这样就相当于把该结点删除了,本题解法基于这种方式。

        首先把要删除的结点(i)的下一个结点(j)的信息复制到结点i,然后把i指向它的下下个结点(即j的下一个结点),然后再把结点j删除,这样就把i删除了。有两个特殊情况:如果要删除的结点i所在的链表中只有一个结点,那么将其置空(null)即可;如果要删除的结点i是链表尾部的最后一个结点,这就需要从链表的头结点开始,顺序遍历链表到该结点,然后将其置空(null),完成删除。

        代码:

      

        可以看到,删除头结点和中间结点的时间复杂度为O(1),而删除尾结点的时间复杂度为O(n),但总的平均时间复杂度还是O(1),符合要求。

        10、链表中倒数第k个结点

        题目:

        输入一个链表,输出该链表中倒数第k个结点。按大多数人的习惯,设链表的尾结点为倒数第一个结点。

        单链表的定义如下:

     

        解答:

        本题采用快慢指针的思想,可以定义两个指针。第一个指针从链表的头结点开始遍历k-1个结点,第二个指针保持不动;当第一个结点遍历到第k个结点时,第二个结点从链表的头结点开始遍历,两个指针的距离始终保持k-1。当第一个指针遍历到链表的尾结点时,此时第二个指针所在的位置正是倒数第k个结点的位置。需要注意的是链表不能为空(null),同时k不能大于链表长度。

        代码:

     

        11、反转链表

        题目:

        定义一个方法,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

        单链表的定义如下:

     

        解答:

        本题需要知道三个结点,即当前结点(node)、当前结点的前一个结点(preNode)、当前结点的下一个结点(nextNode)。

        反转时,将当前结点(node)的下一个结点指向其前一个结点(preNode),这样当前结点(node)与其原来的下一个结点(nextNode)之间发生了断裂,所以需要保存其原来的下一个结点(nextNode)信息。然后将当前结点赋值给前一个结点(preNode),下一个结点赋值给当前结点……以此类推,直到下一个结点为空,此时当前结点就是反转后链表的头结点。

        代码:

       

        12、合并两个排序的链表

        题目:

        输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是递增排序的。

        例如:输入链表1:1->3->5->7

                      链表2:2->4->6->8

                  返回链表:1->2->3->4->5->6->7->8

        单链表的定义如下:

     

        解答:

        本题采用递归方法,利用归并的思想。

        首先定义一个新链表(newList),存放合并后的数据。然后分别遍历两个链表(list1和list2)的头结点,比较其大小。如果list1的头结点小于等于list2的头结点,则将list1的头结点添加到新链表中(newList),然后将list1头结点的下一个结点与list2的头结点作为参数,执行本方法(即递归);反过来如果list1的头结点大于list2的头结点,则将list2的头结点添加到新链表中(newList),然后将list1的头结点与list2头结点的下一个结点作为参数,执行本方法(即递归)……以此类推,不断递归,直到list1或list2为空,然后将另一个列表剩余结点直接放到新链表中即可。

        例如题目中两个链表第一次比较时,list1的头结点1小于list2的头结点2,故list1头结点1放入newList中;然后list1头结点的下一个结点3大于list2的头结点2,故list2头结点2放入newList中;然后list1头结点的下一个结点3小于list2头结点的下一个结点4,故list1头结点的下一个结点3放入newList中……

        代码:

      

        转载请注明出处 http://www.cnblogs.com/Y-oung/p/8933438.html

        工作、学习、交流或有任何疑问,请联系邮箱:yy1340128046@163.com  微信:yy1340128046

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

2020最新微信域名防封技术 微信域名防封系统是如何操作的

相信很多朋友在运营自己产品的网站或者是推广链接的时候,经常会发现运行的好好的网站链接突然就被封了,有一部分因为可能是网站的内容触犯了微信的规则,但是还有很大的一部分被同行恶意投诉...

戚馨逸
27分钟前
11
0
mysql 为什么 SQL 语句不要过多的 join?

第一部分 Linux上查看内存的使用情况该用什么命令 free -mh 可以看到内存或者缓存情况 total 总内存 used 已用内存 free 空闲内存 buff/cache 已使用的缓存 avaiable 可用内存 怎么清理已使...

edison_kwok
28分钟前
17
0
芒果TV的金融野心从未停止

来源|WEMONEY研究室 作者|林小林 芒果TV是真的会讲故事,《乘风破浪的姐姐》不仅是生活的故事更是资本的故事,30位姐姐让一款节目累计播放量飙升10亿,同时让背后的上市公司芒果超媒市值站...

镭射财经
39分钟前
4
0
找到的程序集的清单定义与程序集引用不匹配

问题: I am trying to run some unit tests in a C# Windows Forms application (Visual Studio 2005), and I get the following error: 我试图在C#Windows窗体应用程序(Visual Studio 2......

法国红酒甜
40分钟前
16
0
渗透测试的概念和实战

目录 1. 前言 2. 常见web安全漏洞 3. 思路 3.1渗透测试思路 3.2黑客攻击思路 4. 暴力破解 4.1谷歌黑语法 4.1.1 黑语法inurl:搜索url包含指定字符串 4.1.2 黑语法intitle:搜索网页中的标题名...

六道木
56分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部