我要招人

去企业版

首页 > 试题广场 >

将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复

[单选题]

将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为()

```
O(m)
```
```
O(1)
```
```
O(n)
```
```
O(m+n)
```

查看答案及解析

小虎牙

选A

将长度为n的放在长度为m的链表之后，需要先遍历长度为m的链表，找到链表尾部，这个时间复杂度为O(m)，再将链表尾部的next指针指向长度为n的链表的头结点即可

发表于 2015-11-25 17:04:35 回复(0)

未来即来、

先遍历长度m的链表为O(m)，插入时的O(1)可忽略

发表于 2016-03-01 19:54:23 回复(0)

本命年的Offer！

主要是要先找到长度m链表的尾指针。

发表于 2017-10-23 15:38:08 回复(0)

Ccola

指针遍历长度为m的单链表至行尾，时间复杂度为O（m）

将长度为n的单链表连接在m之后，时间复杂度为O(1)可忽略

总时间复杂度为O（m）

发表于 2016-07-19 18:09:18 回复(0)

Pixelstime

将长度为n的链表作为一个整体插入另外一个链表末尾，需要O(m)，即定位到链表尾部的复杂度。我当时理解错了题目，认为是单元素插入，每次都需要从头定位到尾，那么复杂度为O(n^2)，即n*（2m+n)/2。

发表于 2018-04-17 09:06:40 回复(0)

ThomasCho

这题目又有语病。。“之后”一词应该去掉。不然我会认为，两链连接之后，其算法，是指什么算法呢，两链连接后，要问什么算法呢？

发表于 2017-09-17 21:31:49 回复(0)

大脸猫联萌

单链表，如果我记录了表尾，复杂度是不是就是O(1),一般编写链表的时候，都会把尾指针和头指针同时记录

发表于 2017-04-17 13:28:57 回复(0)

Echo001

忘了找尾指针！！！

发表于 2016-08-29 08:20:11 回复(0)

陕西大水牛

我如果直接知道尾地址，我直接o1就可以啦。就跟删除一样，直接可以o1

发表于 2016-08-19 18:53:27 回复(0)

huixieqingchun

注意读题，不要搞反了。

在链表链接时，要遍历找到链表的尾指针，这个遍历的过程会消耗时间。

发表于 2016-06-04 09:50:35 回复(0)

张星星

从链表头到链表尾需要花O(m)的时间。之后再链接上要O(1)的时间。跟链接上的链表长度无关

所以总共要O(m)的时间

发表于 2016-02-20 20:23:20 回复(0)

提交观点

问题信息

编程基础

来自：迅雷2016研发工程师笔试题

上传者：SunburstRun

难度：

11条回答 229收藏 20558浏览

将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复

问题信息

热门推荐

相关试题