首页 > 其他 > 详细

两个链表的第一个公共节点

时间:2016-03-16 20:51:58      阅读:269      评论:0      收藏:0      [点我收藏+]
技术分享
第一种思路:
    用栈
第二种思路:
    先遍历两个链表,得到各自长度,然后将长的那个链表先往后查找 两长度差的 步数。接着同时向后查找,直到找到相同的节点。

  1. class Solution {
  2. public:
  3. ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
  4. int size1=0,size2=0;
  5. ListNode* p1=pHead1;
  6. ListNode* p2=pHead2;
  7. while(pHead1!=NULL){
  8. size1++;
  9. pHead1=pHead1->next;
  10. }
  11. while(pHead2!=NULL){
  12. size2++;
  13. pHead2=pHead2->next;
  14. }
  15. pHead1=p1;
  16. pHead2=p2;
  17. if(size1>size2){
  18. int n=size1-size2;
  19. while(n--)
  20. pHead1=pHead1->next;
  21. }
  22. else if(size1<size2){
  23. int m=size2-size1;
  24. while(m--)
  25. pHead2=pHead2->next;
  26. }
  27. while(pHead1!=pHead2 &&pHead1!=NULL && pHead2!=NULL){
  28. pHead1=pHead1->next;
  29. pHead2=pHead2->next;
  30. }
  31. return pHead1;
  32. }
  33. };






两个链表的第一个公共节点

原文:http://www.cnblogs.com/zhxshseu/p/5284980.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!