一道公司面试题解决思路

一道公司面试题
如何判断两个循环链表是否相等？如“aabbcc”和"ccaabb"是相等的。请教有什么比较好的算法？


[解决办法]
根据链表构造有向图?
[解决办法]
用双指针
O(N)复杂度

aabbcc 和 ccaabb
i=0, j=0;
i=0, j=1;
i=0, j=2;
i=1, j=3;
i=2, j=4;
i=3, j=5;
i=4, j=0;(j %= str.Length)
一直能将i走到结尾即相等，否则不等

[解决办法]

探讨

如果是aabbacc
bbaccaa
这种的话，需要在指针j走完第一个a之后把指针i重置为0

[解决办法]
把两个循环链表都变成不循环，如aabbcc变成aabbccaabbcc
ccaabb变成ccaabbccaabb
然后判断变化后的两个链表的最大相同字串长度，如果>=n就相同反之...
复杂度参照最大公告字串复杂度
[解决办法]
想到另一个方法

先把其中一个str = str + str，拼接起来成

然后判断别一个是否存在新拼接的str中就能实现了。
[解决办法]
最次循环memcmp就解决了，比选择最大子串快多了

探讨

事实上，这个算法最麻烦的就是决定起始位置。
九楼所说的“然后判断别一个是否存在新拼接的str中就能实现了”把这个问题一笔带过了，在这个问题上如果没有其他的限制的话，九楼的方法在这个问题上并不好处理。而六楼的方法就不存在这个问题！


引用:
不一致，九楼的方法快多了
如果是两个循环串比较就用九楼的方法
如果是n个循环串比较，就设定规则决定……

查看更多 下一篇