各位看看BAT面试题是否无解故意刁难_java

当前位置：网站建设 > 技术支持

资料来源：网络整理时间：2023/3/5 20:23:06 共计：3601 浏览

各位看看BAT面试题是否无解故意刁难？

楼主多虑了，其实这是一道有解的题。

这道题考量了两方面内容：

1.基本的单链表反转

2.编译器和cpu架构相关知识

看来楼主也主要从事C/C++一类工作吧

楼主的问题类似下图吧：

先来说单链表反转

单链表就是链表结点包含一个指向下一个结点指针的链结构

链表的反转思路也很简单，利用两个临时变量指向当前结点和当前结点的下一个结点，然后逐个翻转next指针即可。需要额外考虑单结点和无结点情况以及首结点next置空。

在这道题中，由于引入了额外指针，我暂且叫它p，如果顺着单链表方向无脑翻转p指针指向，则可能造成链表中部分或者全部结点的p指针被反转多次，很显然需要记录哪些结点的p指针被反转过。

但是题目中限制了链表结点中不包含额外可用的字段该怎么办呢？

这就涉及到编译器和cpu指令处理问题了。

一般的cpu架构（x86系列）在访问内存地址时，偶数地址只需要读一次，而奇数地址需要读两次，因此几乎所有的c编译器都默认将指令地址做偶数字节对齐。

此时，如果你打印所有指针的值（不是指针指向内存的值）时，会发现所有的值对4或对8取余都是0，即4字节对齐（32位系统）或8字节对齐（64位）。

而我们的需求只是标记该结点是否有被反转过，即1个比特足以完成，因此，我们可以对p指针或（或操作）上1表示该结点p指针已反转，而没或1的地址则为未反转。

按照上述方法实现，就可以满足楼主题目中的要求啦。

希望对你有帮助。

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。