转神作：判断两个单链表是否相交（链表中可能有环的情况下）

源地址：http://blog.csdn.net/yff1030/article/details/8587217

原文链接：http://www.cppblog.com/zengwei0771/articles/172700.html

题目描述：判断两个单链表是否相交，如果相交，给出相交的第一个点（链表中可能有环的情况下）

这里是①判断单链表是否有环，并求出环的入口点；②判断两个链表是否相交（链表中无环），并求出相交节点 的文章 
http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html

分析：
①：判断链表1是否有环，并记录其长度L1，尾节点b1（无环），环入口点a1（有环）
②：判断链表2是否有环，并记录其长度L2，尾节点b2（无环），环入口点a2（有环）
③：若一个有环，另一个没环，则判断不相交，结束
④：若两个都没环，则两个尾节点一点是一样的，所以比较两个尾节点是否相同。若不相同则判断不相交，结束；若相同，则到⑥。
⑤：若两个都有环，有如下图三种情况：a1与a2不相等，且不在一个环中，则不相交，结束；a1等于a2，跳到⑥；a1与a2不相等，但在一个环中，对于链表1来说a1是它的相交首节点，对于链表2来说a2是它的相交首节点。 















⑥：对于两个链表重头开始遍历，长链表节点先出发前进(Max(L1,L2)-Min(L1,L2))步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

代码如下：

[cpp] view plaincopy
 
    1. typedef struct Node  
    2.   {  
    3.       int value;  
    4.       Node* pNext;  
    5.   }* List;  
    6.     
    7.   Node* IsListCross(List L1, List L2)  
    8.   {  
    9.       if (L1 == NULL || L2 == NULL)  
    10.      {  
    11.          return NULL;  
    12.      }  
    13.    
    14.      int len1 = 0;                //L1的长度  
    15.      int len2 = 0;                //L2的长度  
    16.      bool L1HasLoop = false;        //L1是否有环  
    17.      bool L2HasLoop = false;        //L2是否有环  
    18.      Node *crossEntry1 = NULL, *crossEntry2 = NULL, *end1 = NULL, *end2 = NULL;  
    19.      Node *pNode1, *pNode2, *pNode3;    //临时节点指针  
    20.    
    21.      //①  
    22.      pNode1 = L1;  
    23.      pNode2 = L1;  
    24.      while (pNode2 && pNode2->pNext)  
    25.      {  
    26.          len1++;  
    27.          pNode1 = pNode1->pNext;  
    28.          pNode2 = pNode2->pNext->pNext;  
    29.          if (pNode1 == pNode2)  
    30.          {  
    31.              L1HasLoop = true;  
    32.              break;  
    33.          }  
    34.      }  
    35.      if (L1HasLoop)  
    36.      {  
    37.          pNode2 = L1;  
    38.          while (pNode1 != pNode2)  
    39.          {  
    40.              len1++;  
    41.              pNode1 = pNode1->pNext;  
    42.              pNode2 = pNode2->pNext;  
    43.          }  
    44.          crossEntry1 = pNode1;  
    45.      }  
    46.      else  
    47.      {  
    48.          pNode3 = pNode1;  
    49.          while (pNode3->pNext)  
    50.          {  
    51.              len1++;  
    52.              pNode3 = pNode3->pNext;  
    53.          }  
    54.          end1 = pNode3;  
    55.          len1++;  
    56.      }  
    57.    
    58.      //②  
    59.      pNode1 = L2;  
    60.     pNode2 = L2;  
    61.      while (pNode2 && pNode2->pNext)  
    62.      {  
    63.          len2++;  
    64.          pNode1 = pNode1->pNext;  
    65.          pNode2 = pNode2->pNext->pNext;  
    66.          if (pNode1 == pNode2)  
    67.          {  
    68.              L2HasLoop = true;  
    69.              break;  
    70.          }  
    71.      }  
    72.      if (L2HasLoop)  
    73.      {  
    74.          pNode2 = L2;  
    75.          while (pNode1 != pNode2)  
    76.          {  
    77.              len2++;  
    78.              pNode1 = pNode1->pNext;  
    79.              pNode2 = pNode2->pNext;  
    80.          }  
    81.          crossEntry2 = pNode1;  
    82.      }  
    83.      else  
    84.      {  
    85.          pNode3 = pNode1;  
    86.          while (pNode3->pNext)  
    87.          {  
    88.              len2++;  
    89.             pNode3 = pNode3->pNext;  
    90.          }  
    91.          end2 = pNode3;  
    92.          len2++;  
    93.      }  
    94.    
    95.      //③  
    96.      if (L1HasLoop != L2HasLoop)  
    97.      {  
    98.          return NULL;  
    99.      }  
    100.     //④  
    101.     else if (L1HasLoop == false)  
    102.     {  
    103.         if (end1 != end2)  
    104.         {  
    105.             return NULL;  
    106.         }  
    107.     }  
    108.     //⑤  
    109.     else  
    110.     {  
    111.         //a1 != a2  
    112.         if (crossEntry1 != crossEntry2)  
    113.         {  
    114.             bool onOneLoop = false;  
    115.             pNode1 = crossEntry1->pNext;  
    116.             while (crossEntry1 != pNode1)  
    117.             {  
    118.                 if (pNode1 == crossEntry2)  
    119.                 {  
    120.                     onOneLoop = true;  
    121.                     break;  
    122.                 }  
    123.                 pNode1 = pNode1->pNext;  
    124.             }  
    125.             //a1 != a2，且不在一个环中  
    126.             if (!onOneLoop)  
    127.             {  
    128.                 return NULL;  
    129.             }  
    130.             //a1 != a2，在一个环中  
    131.             else  
    132.             {  
    133.                 return crossEntry1;  
    134.             }  
    135.         }  
    136.     }  
    137.     //⑥  
    138.     pNode1 = L1;  
    139.     pNode2 = L2;  
    140.     int gap;  
    141.     if (len1 > len2)  
    142.     {  
    143.         gap = len1 - len2;  
    144.         while (gap)  
    145.         {  
    146.             pNode1 = pNode1->pNext;  
    147.             gap--;  
    148.         }  
    149.     }  
    150.     else  
    151.     {  
    152.         gap = len2 - len1;  
    153.         while (gap)  
    154.         {  
    155.             pNode2 = pNode2->pNext;  
    156.             gap--;  
    157.         }  
    158.     }  
    159.     while (pNode1 != pNode2)  
    160.     {  
    161.         pNode1 = pNode1->pNext;  
    162.         pNode2 = pNode2->pNext;  
    163.     }  
    164.     return pNode1;  
    165. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xuhj001/p/3389157.html