单链表面试题总结

2017-04-19 17:02 阅读 408 次 评论 0 条

转载至:http://blog.csdn.net/walkinginthewind/article/details/7393134

常见链表面试题

1.求单链表中结点的个数

注意检查链表是否为空,时间复杂度为O(n)。参考代码如下:

2.反转单链表

从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O(n)。参考代码如下:

3.查找单链表中倒数第K个节点

主要思路就是使用两个指针,先让前面的指针走到正向第k个结点,这样前后两个指针的距离差是k-1,之后前后两个指针一起向前走,前面的指针走到最后一个结点时,后面指针所指结点就是倒数第k个结点。参考代码如下:

4.查找单链表的中间节点

此题可应用于上一题类似的思想。也是设置两个指针,只不过这里是,两个指针同时向前走,前面的指针每次走两步,后面的指针每次走一步,前面的指针走到最后一个结点时,后面的指针所指结点就是中间结点,即第(n/2+1)个结点。注意链表为空,链表结点个数为1和2的情况。时间复杂度O(n)。参考代码如下:

5.从尾到头打印单链表

对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况。时间复杂度为O(n)。参考代码如下:

⒈ 非递归,使用栈:

⒉ 使用递归:

6.合并两个有序链表

这个类似归并排序。尤其注意两个链表都为空,和其中一个为空时的情况。只需要O(1)的空间。时间复杂度为O(max(len1, len2))。参考代码如下:

也有如下递归解法:

7.判断一个单链表是否带环

这里也是用到两个指针。如果一个链表中有环,也就是说用一个指针去遍历,是永远走不到头的。因此,我们可以用两个指针去遍历,一个指针一次走两步,一个指针一次走一步,如果有环,两个指针肯定会在环中相遇。时间复杂度为O(n)。参考代码如下:

8.判断两个单链表是否相交

如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1+len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为O(1)。参考代码如下:

9.求两个单链表相交的第一个交点

对第一个链表遍历,计算长度len1,同时保存最后一个节点的地址。
对第二个链表遍历,计算长度len2,同时检查最后一个节点是否和第一个链表的最后一个节点相同,若不相同,不相交,结束。
两个链表均从头节点开始,假设len1大于len2,那么将第一个链表先遍历len1-len2个节点,此时两个链表当前节点到第一个相交节点的距离就相等了,然后一起向后遍历,知道两个节点的地址相同。

时间复杂度,O(len1+len2)。参考代码如下:

10.已知一个单链表存在环,求进入环中的第一个节点

首先判断是否存在环,若不存在结束。在环中的一个节点处断开(当然函数结束时不能破坏原链表),这样就形成了两个相交的单链表,求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。参考代码如下:

11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted?

对于删除节点,我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点,这种情况需要遍历找到该节点的前一个节点,时间复杂度为O(n)。对于链表,链表中的每个节点结构都是一样的,所以我们可以把该节点的下一个节点的数据复制到该节点,然后删除下一个节点即可。要注意最后一个节点的情况,这个时候只能用常见的方法来操作,先找到前一个节点,但总体的平均时间复杂度还是O(1)。参考代码如下:

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:单链表面试题总结 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情