//寻找两个相交链表的第一个公共节点
// 寻找两个链表的第一个公共节点.cpp : Defines the entry point for the console application.
//
/*
1.最简单的方法就是先顺序访问其中一个链表，在每访问一个节点时，都对另外一个链表进行遍历，看节点是否相等
直到找到一个相等的节点位置，如果链表长度分别是m,n 则时间复杂度为O(mn)
2.我们可以知道如果两个链表有公共节点，那么该公共节点之后的所有节点都是两个链表所共有的，所以长度一定也是
相等的，如果两个链表的总长度是相等的，那么我们对两个链表进行遍历，则一定同时到达第一个公共节点。但是链表
的长度实际上不一定相同，所以我们只需要计算出两个链表的长度之差n，然后让长的那个链表先移动n步，短的链表再
开始向后遍历，这样他们一定同时到达第一个公共节点，我们只需要在向后移动的时候比较两个链表的节点是否相等就
可以获得第一个公共节点。时间复杂度是O(m+n)
*/
#include "stdafx.h"
struct ListNode
{
int m_data;
ListNode *m_pNext;
};
unsigned int ListLength(ListNode* pHead)
{
unsigned int nLength = 0;
ListNode* pNode = pHead;
while(pNode != NULL)
{
++ nLength;
pNode = pNode->m_pNext;
}
return nLength;
}
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
{
// Get the length of two lists
unsigned int nLength1 = ListLength(pHead1);
unsigned int nLength2 = ListLength(pHead2);
int nLengthDif = nLength1 - nLength2;
// Get the longer list
ListNode *pListHeadLong = pHead1;
ListNode *pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}
// Move on the longer list
for(int i = 0; i < nLengthDif; ++ i)
pListHeadLong = pListHeadLong->m_pNext;
// Move on both lists
while((pListHeadLong != NULL) &&
(pListHeadShort != NULL) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
}
// Get the first common node in two lists
ListNode *pFisrtCommonNode = NULL;
if(pListHeadLong == pListHeadShort)
pFisrtCommonNode = pListHeadLong;
return pFisrtCommonNode;
}
/*
已知有两个链表，他们可能相交于某一点，求出该点。
方法1.对于第一个链表，每访问一个节点，对该节点做标记。访问第二个链表，如果该元素已经访问，则第一个这样的元素就是所求点。
由于两个链表都访问了一遍，因此时间复杂度O(m+n),空间复杂度O(m)或O(n)
方法2.我们定义节点的距离为节点到链表开始所经过的节点数。如果两个链表长度相同，则相交节点其在两个链表上的距离一定相等。对于长度不同的两个链表，我们可以采用对齐的方式，使其向长度短的链表对齐。这样就可以应用上面的思路。具体算法如下：
*/
struct node
{
int v;
node *next;
};
/*
返回链表的长度
链表为空 返回0
*/
size_t listLen(node * p)
{
size_t num = 0;
while (p!=NULL)
{
num++;
p = p->next;
}
return num;
}
// 如果找到了 则返回指针 指向公共节点
// 如果不存在 则返回空指针
node * findFirstCommenNode(node * pheada, node * pheadb)
{
size_t lenA = listLen(pheada);
size_t lenB = listLen(pheadb);
node * plistA = pheada;
node * plistB = pheadb;
//调整长度
//plistA 指向较长的一个
if (lenA < lenB)
{
plistB = pheada;
plistA = pheadb;
size_t t = lenA;
lenA = lenB;
lenB = t;
}
while(lenA > lenB)
{
plistA = plistA->next;
--lenA;
}
//一样长了
//寻找公共节点
while (plistA!=NULL && plistA != plistB)
{
plistA = plistA->next;
plistB = plistB->next;
}
return plistA;
}
struct node
{
int v;
node *next;
};
/*
返回链表的长度
链表为空 返回0
*/
size_t listLen(node * p)
{
size_t num = 0;
while (p!=NULL)
{
num++;
p = p->next;
}
return num;
}
// 如果找到了 则返回指针 指向公共节点
// 如果不存在 则返回空指针
node * findFirstCommenNode(node * pheada, node * pheadb)
{
size_t lenA = listLen(pheada);
size_t lenB = listLen(pheadb);
node * plistA = pheada;
node * plistB = pheadb;
//调整长度
//plistA 指向较长的一个
if (lenA < lenB)
{
plistB = pheada;
plistA = pheadb;
size_t t = lenA;
lenA = lenB;
lenB = t;
}
while(lenA > lenB)
{
plistA = plistA->next;
--lenA;
}
//一样长了
//寻找公共节点
while (plistA!=NULL && plistA != plistB)
{
plistA = plistA->next;
plistB = plistB->next;
}
return plistA;
}
/*
算法的空间复杂度O(1)，时间复杂度O(m+n)，效果不错吧。
如果链表中有环会怎么样呢？
上面的算法会死循环的。在求解链表长度的时候就会死循环了。但是这样的问题该如何解决呢。
首先的解决访问带环链表的问题。如果访问带环链表访问解决了，那么使用方法一就可以解决原问题，但是能不用优化到算法二的空间复杂度呢。算法二的思路还是很可取的，这里可不可以继续使用呢？
我们定义链表的长度为链表中节点的个数，如果链表相交，应该还是具有算法二的性质。因此，修改求取链表长度的算法，使用算法二。具体算法如下：
*/
// 如果找到了 则返回指针 指向公共节点
// 如果不存在 则返回空指针
// pheada 指向第一个链表的头
// pheadb 指向第二个链表的头
node * findFirstCommenNode(node * pheada, node * pheadb)
{
size_t lenA = listLen(pheada);
size_t lenB = listLen(pheadb);
node * plistA = pheada;
node * plistB = pheadb;
//调整长度
//plistA 指向较长的一个
if (lenA < lenB)
{
plistB = pheada;
plistA = pheadb;
size_t t = lenA;
lenA = lenB;
lenB = t;
}
while(lenA > lenB)
{
plistA = plistA->next;
--lenA;
}
//一样长了
//寻找公共节点
while (lenA !=0 && plistA != plistB)
{
plistA = plistA->next;
plistB = plistB->next;
--lenA;//这里进行修改,免得进入环后死循环
}
return plistA;
}
/*
问题：
两个单向链表，可能存在公共节点。如何判断是否存在公共节点，并找出它们的第一个公共结点。
思想：
1. 如果两个链表相交，则从相交点开始，后面的节点都相同，即最后一个节点肯定相同；
2. 从头到尾遍历两个链表，并记录链表长度，当二者的尾节点不同，则二者肯定不相交；
3. 尾节点相同，如果A长为LA，B为LB，如果LA>LB,则A前LA-LB个先跳过，
然后二者一起向后遍历，直到遇到相同的节点；LA<LB类似处理
因为第一个公共节点距起始节点的距离start_a满足： LA - start_a == LB - start_b。
*/
//简单代码：
const ListNode* FirstCommonNode(const ListNode* listA, const ListNode* listB)
{
if(listA==NULL || listB==NULL) return NULL;
int LA=1,LB=1;//A，B链表长度
const ListNode* curA = listA, *curB = listB;
while(curA->next)//求A尾节点
{++LA; curA = curA->next;}
while(curB->next)//求B尾节点
{++LB; curB = curB->next;}
if(curA != curB) return NULL;//尾节点不相同，则没有相交
curA = listA;curB = listB;
if(LA > LB)//
{
for(int i=0; i<LA-LB; ++i)
curA = curA->next;
}
else
{
for(int i=0; i<LB-LA; ++i)
curB = curB->next;
}
while(curA && curA!=curB)
{
curA = curA->next;
curB = curB->next;
}
return curA;
}
//简单测试代码：
void CreateJointList(const string* strA, int sizeA,const string* strB ,int sizeB,
const string* strC,int sizeC,ListNode** listA,ListNode** listB)//创建两个相交的链表
{
ListNode* rootA = new ListNode(strA[0]);
ListNode* rootB = new ListNode(strB[0]);
*listA = rootA; *listB = rootB;
for(int i=1; i<sizeA; ++i)
{
rootA->next = new ListNode(strA[i]);
rootA = rootA->next;
}
for(int i=1; i<sizeB; ++i)
{
rootB->next = new ListNode(strB[i]);
rootB = rootB->next;
}
ListNode* tmp = new ListNode(strC[0]);
rootA->next = tmp;
rootB->next = tmp;
for(int i=1; i<sizeC; ++i)
{
tmp->next = new ListNode(strC[i]);
tmp = tmp->next;
}
}
ListNode *headA,*headB;
const int SizeA = 6,SizeB = 7,SizeC = 5;
const string A[SizeA] = {"I","am","an","List","named","A"};
const string B[SizeB] = {"I","am","also","an","List","named","B"};
const string C[SizeC] = {"this","part","is","in","Comman"};
CreateJointList(A,SizeA,B,SizeB,C,SizeC,&headA,&headB);
PrintList(headA);
PrintList(headB);
const ListNode *node = FirstCommonNode(headA, headB);
if(node != NULL)
cout<<"\nCommon Node : \t"<<node->value<<endl;
}
/*
扩展2：求两个链表相交的第一个节点
思路：在判断是否相交的过程中要分别遍历两个链表，同时记录下各自长度。
*/
Node* step( Node* p, Node* q)
{
if ( !p || !q ) return NULL;
int pLen = 1;
int qLen = 1;
bool result = false;
while( p->next )
{
pLen++, p = p->next;
}
while( q->next )
{
qLen++, q = q->next;
}
result = ( p == q );
if ( result )
{
int steps = abs( pLen - qLen);
Node* head = pLen > qLen ? p : q;
while ( steps ) //对齐处理
{
head = head->next, steps--;
}
pLen > qLen ? p = head : q = head;
while ( p != q )
{
p = p->next, q = q->next;
}
reutrn p;
}
return NULL;
}
/*
下面转载来源:http://blog.chinaunix.net/u2/63031/showart_1003241.html
深信服一道笔试：如何判断两个单向链表是否有相交，并找出交点。
题比较简单，单向链表有交点意思就是交点后的节点都是一样的了。
*/
NODE* FindNode(NODE* pHead1, NODE* pHead2)
{
NODE* p1 = pHead1;
NODE* p2 = pHead2;
int i = 1, j = 1, k = 0, f = 0;
if(pHead2 == NULL || pHead2 == NULL)
{
return NULL;
}
while(p1->next != NULL)
{
p1 = p1->next;
i++;
}
while(p2->next != NULL)
{
p2 = p2->next;
j++;
}
if(p1 != p2)
{
return NULL;
}
else
{
p1 = pHead1; // 1
p2 = pHead2;
f = fabs(i, j);
if(i > j) // 2
{
for(k=0; k<</SPAN>f; k++)
{
p1 = p1->next;
}
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
else
{
for(k=0; k<</SPAN>f; k++)
{
p2 = p2->next;
}
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
}
}
/*
http://cache.baiducontent.com/c?m=9d78d513d9d430aa4f9995690c66c0171a43f0152bd6a0020fde843c97735a315017e0ac57240774d0d20b1116ae394b9b842105351450c18cb8f85ddccb8558289f5632671df65662d40ed9b85124b137e65afedf69f0bb8025e3a4c5a7db4352ba44750c9786f84d7013dd18f10076a3f89612531952adec4378e2092974ca3440c106a2bc617907f6a780035bc35d813d0cd6b265ee6347a214d01b487410a01db30e532532e34566bb062a04e5b11bb874&p=8b2a9715d9c340af00fcd312564bcd&newp=c0759a45d7c305dd0caae62d021494231610db2151d3d1113ba6c70fe1&user=baidu&fm=sc&query=%C7%F3%C1%BD%B8%F6%C1%B4%B1%ED%CF%E0%BD%BB%B5%C4%B5%DA%D2%BB%B8%F6%BD%DA%B5%E3&qid=&p1=2
1，在第一次遍历完链表后，进行第二次遍历，需要把指针再次初始化；看见网上一些人给的例子没有再次初始化显然是错误的；再调用NULL的next不死才怪！
2，小优化。循环和判断，把判断放在外面；如果把i和j大小判断放在里面的话就意味着循环多少次，判断就执行多少次；当然这样做的唯一不足就是代码 多了点；还有for循环之前的对f的赋值，有的为了简便直接放在for语句里面，不过同样道理，放在for循环里面，就执行了n次的fabs；拿出来赋 值，只赋值一次就OK。
友情提示：养成写高效代码的习惯，不能图简便，觉得代码越少就越牛！
*/