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

板块导航

浏览  : 3695
回复  : 21

[社区公告] 【UDN算法每周一战】判断一个链表是否为回文结构

[复制链接]
born的头像 楼主
发表于 2015-11-18 10:00:21 | 显示全部楼层 |阅读模式
本帖最后由 born 于 2015-12-15 14:41 编辑

UDN算法每周一战是UDN技术社区推出的算法交流活动。

算法交流要求智力与艺术想结合,不仅实现方式精巧,更要求展现形式华丽多彩。

【题目】

给定一个链表的头节点head,请判断该链表是否为回文结构。

例如:
1->2->1,返回true
1->2->2->1,返回true
15->6->15,返回true
1->2->3,返回false

请使用JavaScript判断如下链表是否为回文结构:
1->2->11->2->11->2->11->2->11->2->11->2->11->2->11->2->11->1->11->2->11->2->11->2->11->2->11->2->11->2->1


【要求】
1. 请将代码发布在runjs.udn.yyuap.com,然后回复本帖,给出代码的链接地址。
2.实现题目功能,打印代码运行耗时


【评奖规则】

1.实现功能且耗时最短者胜出


【答题周期】

11月18日~11月24日23点59分59秒

【奖品】

IT类图书一本,用户可从我们的UDN赠书活动中任选一本。书单如下:

《失控》
《三体I》
《三体II》
《三体III》
《锋利的jQuery(第2版)》
《JavaScript DOM编程艺术(第2版)》
《精益思想(白金版)》   
《褚橙你也学不会》
《Java并发编程的艺术》
《React:引领未来的用户界面开发框架》
Docker开发实践》
《深入理解Java虚拟机:JVM高级特性与最佳实践》
《京东技术解密》
《R语言实战》
《Open Stack设计与实现》
《数据挖掘与数据化运营实战 思路、方法、技巧与应用》
《海量运维、运营规划之道》
《Python自动化运维:技术与最佳实践》
《Spark大数据处理技术》
《ElasticSearch 可扩展的开源弹性搜索解决方案》
《淘宝技术这十年》
《大规模分布式存储系统:原理解析与架构实战》
《Hadoop权威指南(第3版 修订版)》
《Redis设计与实现》
《大规模Java平台虚拟化与调优》
《Docker源码分析》   
《用户体验至上:移动UI完美视觉设计法则》
《移动App测试实战:顶级互联网企业软件测试和质量提升最佳实践》
《torm企业级应用:实战、运维和调优》
《Flume日志收集与MapReduce模式》
《网络安全监控实战:深入理解事件检测与响应》
《Hadoop YARN权威指南》
《人人都是网站分析师:从分析师的视角理解网站和解读数据》
《Splunk实践指南》
《Docker技术入门与实践》
《Python自动化运维:技术与最佳实践》
《构建高可用Linux服务器(第3版)》
《Kali渗透测试技术实战》
《Node.js权威指南》
《JavaScript性能优化:度量、监控与可视化》

本期结果:@dulei
获奖理由:最早发布了实现代码

温情提示:UDN是首次举办类似线上算法活动,如有疑问或者觉得活动不合理的地方还请及时指正,我们将给予被采纳意见的提出者100U币的奖励,谢谢~

发表于 2015-11-18 11:44:04 | 显示全部楼层
我想问一下,为啥每次都必须是js语言呀
点评 ( 1 ) 收起 / 展开点评

born 2015年11月19日 09:15 详情 回复

因为runjs.udn.yyuap.com 只支持JS语言

使用道具 举报

回复

发表于 2015-11-18 12:28:18 | 显示全部楼层
单链表么?链表结构呢。
使用道具 举报

回复

发表于 2015-11-18 16:33:15 | 显示全部楼层
两个指针,一个一次next,另一个两次next。一个走到链表尾时,另一个正好在链表中间。
然后一个队列,一个栈,各放一半,分别取数比较。
大概的思路吧。
使用道具 举报

回复

发表于 2015-11-18 16:42:23 | 显示全部楼层
使用道具 举报

回复

发表于 2015-11-18 19:57:55 | 显示全部楼层
使用道具 举报

回复

发表于 2015-11-18 22:34:52 | 显示全部楼层
http://runjs.udn.yyuap.com/detail/o4r8d0yk


设计思路:
1、定义两个变量a,b, a以步长1,b以步长2同时遍历单向链表,当b到达链表末尾时,a正好在链表中间位置(不区分奇偶长度);
2、第一次遍历结束后,构造一个堆栈,再次让a开始遍历,并把遍历到的元素推入堆栈中;
3、从堆栈中弹出元素,与原始的链表比较,如果堆栈中的元素都弹出且与原始链表对应的元素相等,则表示为回文链表,当任何位置不相同,则不是回文链表;
使用道具 举报

回复

born的头像 楼主
发表于 2015-11-19 09:15:26 | 显示全部楼层
四个脚印 发表于 2015-11-18 11:44
我想问一下,为啥每次都必须是js语言呀

因为runjs.udn.yyuap.com 只支持JS语言
使用道具 举报

回复

发表于 2015-11-19 09:48:37 | 显示全部楼层
使用道具 举报

回复

发表于 2015-11-19 15:06:43 | 显示全部楼层
上一期算2进制1的个数的楼主说只有1个人算对,我怎么看是没人算对,(12345678987654321和12345678987654320的结果一样??)在上个帖子的没人回,我也不多说能说的都在上个帖子http://udn.yyuap.com/thread-69709-1-1.html,就贴2张计算器的图
1.jpg
2.jpg
点评 ( 1 ) 收起 / 展开点评

born 2015年11月20日 10:00 详情 回复

测试数据:n=12345678987654321 n=-12345678987654321 哥,你把测试数据弄错了

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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