分类： 项目管理
2011-05-17 21:20:31
编程判断两个链表是否相交
问题：给出两个单向链表的头指针，比如head1和head2，判断这两个链表是否相交。这里给出简化问题，假设两个链表均不带环。
解答：首先了解一下这个问题的工程实践，例如在一个大的系统中，如果出现两个链表相交的情况，一旦程序释放了其中的一个链表的所有节点，那样就会造成第二个链表信息的丢失。因此，我们需要在释放一个链表之前知道是否有其他链表与当前链表相交。
直观的想法：
判断第一个链表的每一个节点是否在第二个链表中，这需要O(Length(head1)*Length(head2))的时间复杂度，需要改进；
利用计数的方法：
如果两个链表相交，那么这两个链表存在共同的节点。而节点地址是节点的唯一标识。因此，我们只需判断两个链表中是否存在地址一致的节点即可。一个简单的方法是对第一个链表的节点地址进行哈希排序，建立哈希表，然后针对第二个链表的每个节点的地址查询哈希表，如果它在哈希表中出现说明两个链表相交。这个方法的时间复杂度是O(Length(head1)+Length(head2))，但是它同时需要附加O(Length(head1))的存储空间，以存放哈希表。
对问题进行转化：
由于两个链表没有环，我们可以将第二个链表接在第一个链表后面，如果得到的链表有环，说明这两个链表相交。否则，这两个链表不相交。因此，这就把问题转化为判断链表是否有环了。
如果这个新链表有环，那么第二个链表的表头一定在环上，我们从第二个链表开始遍历，看是否会回到起始点就可以判断出来了。最后我们还得记住将链表恢复原状，去掉第一个链表指向第二个链表表头的指针。
这个算法的时间复杂度是线性的，且只需要常数的空间。
问题的最终解决方案：
抓住本质：如果两个没有环的链表相交于某一点，那么在这个节点之后的所有节点都是这两个链表所共有的。如果两个链表相交，那么最后一个节点一定是共有的，因此，先遍历第一个链表，记住最后一个节点；再遍历第二个链表，到最后一个节点时和第一个链表的最后节点比较，如果相同，则相交，否则不相交。
这个算法时间复杂度是O(Length(head1)+Length(head2))，且仅用了一个额外的指针来存放第一个链表的最后一个节点。
完整代码如下：
#include
#include
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
void InitList(ListNode** head)
{
*head = (ListNode*)malloc(sizeof(ListNode));
(*head)->m_pNext = NULL;
}
void InsertList(ListNode* head, int data)
{
assert(head != NULL);
ListNode* pNewNode = (ListNode*)malloc(sizeof(ListNode));
pNewNode->m_nKey = data;
pNewNode->m_pNext = head->m_pNext;
head->m_pNext = pNewNode;
}
bool IsListIntercource(ListNode* head1, ListNode* head2)
{
if(head1 == NULL || head2 == NULL)
return false;
ListNode* pNode = head1;
while(pNode->m_pNext != NULL)
{
if(pNode->m_pNext->m_pNext == NULL)
{
pNode = pNode->m_pNext;
break;
}
pNode = pNode->m_pNext;
}
if((head2->m_pNext == NULL) && (pNode == head2))
return true;
while(head2->m_pNext != NULL)
{
if(head2->m_pNext->m_pNext == NULL)
{
if(pNode == head2->m_pNext)
return true;
else
return false;
}
head2 = head2->m_pNext;
}
}
int main()
{
ListNode* pListHead1 = NULL;
ListNode* pListHead2 = NULL;
InitList(&pListHead1);
InitList(&pListHead2);
//建立两个链表
for(int i=9; i>=0; i--)
{
InsertList(pListHead1, i);
InsertList(pListHead2, i);
}
//新建一个节点
ListNode* pListNode = (ListNode*)malloc(sizeof(ListNode));
pListNode->m_nKey = 100;
pListNode->m_pNext = NULL;
ListNode* pTemp = pListHead1;
while(pTemp->m_pNext != NULL)
{
pTemp = pTemp->m_pNext;
}
pTemp->m_pNext = pListNode; //将新节点接在链表后面
pTemp = pListHead2;
while(pTemp->m_pNext != NULL)
{
pTemp = pTemp->m_pNext;
}
pTemp->m_pNext = pListNode; //将新节点接在链表后面
//判断两个链表是否相交
if(IsListIntercource(pListHead1, pListHead2))
{
std::cout<<"两个链表相交"<
}
else
{
std::cout<<"两个链表不相交"<
}
system("pause");
return 0;
}
=======================================================
扩展问题：两个单向链表，编程找出它们的第一个公共节点
解答：在上一题中已经提到，如果两个链表有一个公共节点，那么该公共节点之后的所有节点都是重合的，那么，它们的最后一个节点必然也是重合的。因此，判断两个链表是否有重复部分，只要分别遍历两个链表的最后一个节点。如果两个尾节点是一样的，那么两个链表重合，否则两个链表没有公共的节点。
顺着上面的思路，顺序变量两个链表到尾节点时，我们并不能保证在两个链表上同时到达尾节点。这是因为两个链表长度不一定一样。如果假设链表1比链表2多x个节点，我们可以先在链表1上遍历前x个节点，之后再和链表2同步遍历，这样就可以保证同时到达最后一个节点了。由于两个链表从第一个公共节点开始到链表的尾节点部分都是重合的，因此，它们肯定也同时到达第一个公共节点。在遍历中，第一个相同的节点就是第一个公共的节点。
最后我们的方案是：先分别变量两个链表得到它们的长度，并求出两个长度之差x。在长链表上先遍历x次之后，再同步变量第二个链表，直到找到相同的节点或一直到链表结束。
该算法的时间复杂度是O(Length(head1)+Length(head2))。
完整代码如下：
#include
#include
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
void InitList(ListNode** head)
{
*head = (ListNode*)malloc(sizeof(ListNode));
(*head)->m_pNext = NULL;
}
void InsertList(ListNode* head, int data)
{
assert(head != NULL);
ListNode* pNewNode = (ListNode*)malloc(sizeof(ListNode));
pNewNode->m_nKey = data;
pNewNode->m_pNext = head->m_pNext;
head->m_pNext = pNewNode;
}
bool IsListIntercource(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL || pHead2 == NULL)
return false;
ListNode* pNode = pHead1;
while(pNode->m_pNext != NULL)
{
if(pNode->m_pNext->m_pNext == NULL)
{
pNode = pNode->m_pNext;
break;
}
pNode = pNode->m_pNext;
}
if((pHead2->m_pNext == NULL) && (pNode == pHead2))
return true;
while(pHead2->m_pNext != NULL)
{
if(pHead2->m_pNext->m_pNext == NULL)
{
if(pNode == pHead2->m_pNext)
return true;
else
return false;
}
pHead2 = pHead2->m_pNext;
}
}
int ListLength(ListNode* pHead)
{
int nLength = 0;
ListNode* pNode = pHead;
while(pNode->m_pNext != NULL)
{
++nLength;
pNode = pNode->m_pNext;
}
return nLength;
}
//核心算法，获得第一个相交的节点
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
ListNode* pListHeadLong = NULL;
ListNode* pListHeadShort = NULL;
int nLen1 = ListLength(pHead1);
int nLen2 = ListLength(pHead2);
int nDiff = nLen1 - nLen2;
if(nDiff >= 0)
{
pListHeadLong = pHead1;
pListHeadShort = pHead2;
}
else
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nDiff = -(nDiff);
}
//长链表先遍历nDiff个节点
for(int i=0; i
pListHeadLong = pListHeadLong->m_pNext;
//接着在两个链表上同时遍历
while((pListHeadLong != NULL) &&
(pListHeadShort != NULL) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
}
//返回第一个相交的节点
ListNode* pFirstCommonNode = NULL;
if(pListHeadLong == pListHeadShort)
pFirstCommonNode = pListHeadLong;
return pFirstCommonNode;
}
int main()
{
ListNode* pListHead1 = NULL;
ListNode* pListHead2 = NULL;
InitList(&pListHead1);
InitList(&pListHead2);
//建立两个链表
for(int i=9; i>=0; i--)
{
InsertList(pListHead1, i);
InsertList(pListHead2, i);
}
//新建一个节点
ListNode* pListNode = (ListNode*)malloc(sizeof(ListNode));
pListNode->m_nKey = 200;
pListNode->m_pNext = NULL;
ListNode* pTemp = pListHead1;
while(pTemp->m_pNext != NULL)
{
pTemp = pTemp->m_pNext;
}
pTemp->m_pNext = pListNode; //将新节点接在链表后面
pTemp = pListHead2;
while(pTemp->m_pNext != NULL)
{
pTemp = pTemp->m_pNext;
}
pTemp->m_pNext = pListNode; //将新节点接在链表后面
ListNode* pCommon = FindFirstCommonNode(pListHead1, pListHead2);
std::cout<<"第一个相交的节点值是："<
system("pause");
return 0;
}
小记：
我老婆再思考若干时间后，居然想到了 最终想法。
