随笔 - 2, 文章 - 1, 评论 - 0, 引用 - 0
数据加载中……

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

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

这里是①判断单链表是否有环，并求出环的入口点；②判断两个链表是否相交（链表中无环），并求出相交节点 的文章 
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))步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

代码如下：
  1typedef struct Node
  2{
  3    int value;
  4    Node* pNext;
  5}* List;
  6
  7Node* 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    //⑥
139    pNode1 = L1;
140    pNode2 = L2;
141    int gap;
142    if (len1 > len2)
143    {
144        gap = len1 - len2;
145        while (gap)
146        {
147            pNode1 = pNode1->pNext;
148            gap--;
149        }
150    }
151    else
152    {
153        gap = len2 - len1;
154        while (gap)
155        {
156            pNode2 = pNode2->pNext;
157            gap--;
158        }
159    }
160    while (pNode1 != pNode2)
161    {
162        pNode1 = pNode1->pNext;
163        pNode2 = pNode2->pNext;
164    }
165    return pNode1;
166}
：

posted on 2012-04-25 13:34 阿伟 阅读(3638) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理