寻找两个相交链表的第一个公共节点

时间:2022-06-01 19:01:52

//寻找两个相交链表的第一个公共节点
// 寻找两个链表的第一个公共节点.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。
友情提示:养成写高效代码的习惯,不能图简便,觉得代码越少就越牛!
*/