UDN-企业互联网技术人气社区

板块导航

浏览  : 1365
回复  : 0

[面试技巧] 经典面试题之链表

[复制链接]
舞操的头像 楼主
发表于 2015-12-28 18:42:43 | 显示全部楼层 |阅读模式

  《程序员面试金典》p49,2.6, 求单链表环路的入口结点。

  相关题目:给定两个单链表,求他们的共同交点。

  解法:

  (1)利用栈,空间复杂度高

  (2)先对两个链表分别作就地反转,然后再一次判断

  (3)先分别遍历两个链表,如果能遍历到相同的尾结点,则两个链表相交,同时记录下两条链表的长度longlength和shortlength,然后用两个指针fast和slow;fast先走(longlength-shortlength)步,然后他们再同时走,到相同时就是第一个相交结点

  (4)将两个链表首尾相连,然后转换为“求单链表中环路的开头结点”的问题。时间复杂度O(M+N)

  给定单链表头结点,删除链表中倒数第k个结点

  分析:这道题可转换为查找链表中倒数第k+1个结点;只需要注意k+1和链表的长度,注意其中的错误检查即可
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部