见龙卸甲结局:一步一步写算法（之链表重合）

来源：百度文库 编辑：中财网 时间：2024/05/01 22:28:59

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】


链表重合是一个好玩的问题。原题目是这样的：有两个链表，那么如何判断这两个链表是不是重合的？至于这个链表在什么时候重合的，这不重要，关键是判断这个链表究竟有没有重合。究竟有什么方法呢？

最简单的方法就是查看两者有没有共同点。那么依次判断就行了。

view plaincopy to clipboardprint?

  1. int find_node_in_link(LINK_NODE* pLink, LINK_NODE* pNode)
  2. {
  3. while(pLink){
  4. if(pLink == pNode)
  5. return 1;
  6. pLink = pLink->next;
  7. }
  9. return 0;
  10. }
  12. STATUS find_if_link_merge(LINK_NODE* pLinkOne, LINK_NODE* pLinkTwo)
  13. {
  14. LINK_NODE* pHead;
  16. if(NULL == pLinkOne || NULL == pLinkTwo)
  17. return FALSE;
  19. pHead = pLinkTwo;
  20. while(pHead){
  21. if(find_node_in_link(pLinkOne, pHead))
  22. return TRUE;
  23. pHead = pHead->next;
  24. }
  26. return FALSE;
  27. }
另外一种方法就是计数的方法，既然链表在某处重合，那么此点访问的次数就是2，所以我们可以依次把两个链表遍历一下，最后查看有没有节点的count为2即可。

view plaincopy to clipboardprint?

  1. typedef struct _LINK_NODE
  2. {
  3. int data;
  4. int count;
  5. struct _LINK_NODE* next;
  6. }LINK_NODE;
  8. void process_all_link_node(LINK_NODE* pNode)
  9. {
  10. assert(NULL != pNode);
  12. while(pNode){
  13. pNode->count ++;
  14. pNode = pNode->next;
  15. }
  16. }
从计数的方法，我们可以发现如果两个链表是重合的，那么他们的最后一个节点必然是相同的，所以只要判断最后一个节点是否相同即可。

view plaincopy to clipboardprint?

  1. STATUS find_if_link_merge(LINK_NODE* pLinkOne, LINK_NODE* pLinkTwo)
  2. {
  3. assert(NULL != pLinkOne && NULL != pLinkTwo);
  5. while(pLinkOne->next) pLinkOne = pLinkOne->next;
  6. while(pLinkTwo->next) pLinkTwo = pLinkTwo->next;
  8. return (pLinkOne == pLinkTwo) ? TRUE : FALSE;
  9. }

总结：

1）链表重合的题目虽然简单，但是从不同的角度可以有不同的答案；

2）本题目来自《编程之美》， 如果对解法还有兴趣的朋友可以参考《编程之美》。

链表综合算法设计 设计一个用链表表示的简单选择排序的算法，并实现之（试验报告） 怎样才能把算法写好啊？ 写者问题的算法 春秋人生之重合 世纪文学哪有的下 如何一步一步的提高写公文材料的水平？ 链表的冒泡排序算法 程序调度（时间片轮转算法）用C语言程序怎么写啊？？谢谢 程序调度（时间片轮转算法）用C语言程序怎么写啊？？谢谢 程序调度（时间片轮转算法）用C语言程序怎么写啊？？谢谢 用C语言写一个排序算法。 帮忙 写个算法 用C++语言 通过中心对称可以互相重合的汉字有()和（） 求常用的单向链表的遍历算法 数据结构链表的插入,删除,查找,计数操作算法 在24小时内，两针重合多少次（不计开始在0点时重合的那一次） 瓶装的营养快线的百分百中奖，怎么得奖，一步一步写清THS qq空间开场的FLASH代码什么，谁能一步一步慢慢写清楚 谢 了 政审表之入伍申请表怎么写？？ 我家没迅雷怎么下载（一步一步说清楚哦） 山市是怎么一步一步变化的（用原句回答） 根号9等于多少？（一步一步的演算出来，谢谢！） 根号5等于多少？（一步一步的演算出来，谢谢！） 根号45等于多少？（一步一步的演算出来，谢谢！）