今天在逛csdn无意中看到的，很不错的书。之前看过 程序员面试攻略 那本书，觉得不错。而且我在找工作面试的过程中，确实就遇到过很多类似的。现在看了这本书，更是如获珍宝。 说说第4期的 判断链表相交的问题：
之前有过类似的问题就是判断一个链表有没有环，那个很简单，设置2个不同的步进指针就可以了。看到这个判断相交的问题，我就说说我对第一个扩展问题的想法吧
如果有环且相交的话，那这2个链表的形式就象一个带2跟挂带的手镯一样的了。中间是个死循环，所以判断链表结尾是行不通的，所以至少需要2个指针来作为退出条件的判断。所以我的思路是： 从A出发2个指针，一个步进一，设为A1，一个步进二,设为A2，从B出发2个指针，同样一个步进一，B1,一个步进二，B2。
A的2个指针先出发，如果有A2为空了，则没有环。A2守在这儿,等B的指针。 如果A1 == A2, 有环，且相等的地方必为环上的某一个结点。把A2指向A1的下一个结点（这样确保B的指针能在第一时间内与A的指针碰头，如果相交的话）。同样，守在这边。
B的2个指针出发，边走边判断和B2是否与A1和A2中的一个相等。如果相等则相交。同时要判断B1 是否等于 B2。如果相等则B上有环并且与A没有相交。B2为空，判断是否与A2相等，如相等则相交。不等则不相交。 |
[返回] 计算机科学论坛 →
计算机技术与应用 → 『 编程心得 』 → (第四期获奖名单公布，最新4节的电子版pdf已开放下载) 预览电子版，写书评，赢取《编程之美—微软技术面试心得》(微软亚洲研究院邹欣等主编)，每周送出3本，机会多多！，欢迎参加由博文视点和本站联合举办的有奖征集书评活动
(订阅本版)
2008/5/8 13:31:00
新浪微博
顶端