当前位置：首页 → 问答吧 → 一道公司面试题

一道公司面试题

时间：2011-11-07

来源：互联网

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

作者: jiehao 发布时间: 2011-11-07

根据链表构造有向图?

作者: zhaghi 发布时间: 2011-11-07

用双指针
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走到结尾即相等，否则不等

作者: keeya0416 发布时间: 2011-11-07

引用 2 楼 keeya0416 的回复:

用双指针
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

作者: ohmygirl 发布时间: 2011-11-07

想不出什么好算法，就2L的算法，加3L的改进，复杂度肯定不止O(N)了，判断相等没什么捷径的

作者: funfenffun 发布时间: 2011-11-07

引用 3 楼 ohmygirl 的回复:

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

引用 4 楼 funfenffun 的回复:

想不出什么好算法，就2L的算法，加3L的改进，复杂度肯定不止O(N)了，判断相等没什么捷径的

2L写的是一个较简单的例子
当i，j所指字符不同时是不必要 i=0 的；要活学活用KMP

作者: keeya0416 发布时间: 2011-11-07

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

作者: xueyong4712816 发布时间: 2011-11-07

"需要在指针j走完第一个a之后把指针i重置为0"，不太明白，能说具体一下吗？比如说仍然是aabbacc和bbaccaa

i = 0, j = 0;
i = 0, j = 1;
i = 0, j = 2;
然后i又等于0，j = 3吗？
i = 0, j = 3;
i = 0, j = 4;
... ...

引用 3 楼 ohmygirl 的回复:

引用 2 楼 keeya0416 的回复:

用双指针
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
bba……

作者: jiehao 发布时间: 2011-11-07

这个貌似可以！

引用 6 楼 xueyong4712816 的回复:

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

作者: jiehao 发布时间: 2011-11-07

想到另一个方法

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

然后判断别一个是否存在新拼接的str中就能实现了。

作者: yangball 发布时间: 2011-11-07

引用 9 楼 yangball 的回复:
想到另一个方法

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

然后判断别一个是否存在新拼接的str中就能实现了。

高手。。。

作者: myhaikuotiankong 发布时间: 2011-11-07