单链公共节点问题

  1 /************************************
  2 File Name:ListFirstSameNode.cpp
  3 Author: godfrey
  4 Created Time: 2016/04/29
  5 *************************************/
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <cstdlib>
  9 using namespace std;
 10 
 11 typedef struct tagSNode{
 12     int value;
 13     tagSNode* pNext;
 14 
 15     tagSNode(int v):value(v),pNext(NULL) {}
 16 }SNode;
 17 //打印链表
 18 void Print(SNode* pHead){
 19     SNode* p = pHead->pNext;
 20     while(p){
 21         cout<<p->value<<" ";
 22         p = p->pNext;
 23     }
 24     cout<<endl;
 25 }
 26 //删除分配结点空间
 27 void Destroy(SNode* pHead){
 28     SNode* p;
 29     while(pHead){
 30         p = pHead->pNext;
 31         delete pHead;
 32         pHead = p;
 33     }
 34 }
 35 
 36 //计算链表长度
 37 int CalcListLength(SNode* p){
 38     int nLen = 0;
 39     while(p){
 40         p = p->pNext;
 41         nLen++;
 42     }
 43     return nLen;
 44 }
 45 
 46 //找到链表第一个公共节点
 47 SNode* FindListFirstSameNode(SNode* p1Head,SNode* p2Head){
 48     //指向第一个有效节点
 49     SNode* p1 = p1Head->pNext;
 50     SNode* p2 = p2Head->pNext;
 51     //定义长度长短的链表，默认p1长
 52     SNode* pLonger = p1;
 53     SNode* pShorter = p2;
 54     //计算链表长度
 55     int p1Len = CalcListLength(p1);
 56     int p2Len = CalcListLength(p2);
 57     int LenDif = p1Len-p2Len;
 58     //更改长度长的链表
 59     if(p1Len<p2Len){
 60         pLonger = p2;
 61         pShorter = p1;
 62         LenDif = p2Len-p1Len;
 63     }
 64     //空转LenDif次
 65     for(int i=0;i<LenDif;i++){
 66         pLonger = pLonger->pNext;
 67     }
 68     //齐头并进，找到第一个公共节点，找不到返回NULL
 69     while(pLonger && pShorter){
 70         if(pLonger == pShorter)
 71             return pShorter;
 72         pLonger = pLonger->pNext;
 73         pShorter = pShorter->pNext;
 74     }
 75     return NULL;
 76 }
 77 
 78 int main()
 79 {
 80     int data[] = {1,2,3,4,5,6,7,8,9};
 81     SNode* p1Head = new SNode(0);
 82     SNode* p2Head = new SNode(0);
 83     int size = sizeof(data)/sizeof(int);
 84     for(int i=size-1;i>=0;i--){
 85         SNode* p = new SNode(data[i]);
 86         p->pNext = p1Head->pNext;
 87         p1Head->pNext = p;
 88         if((i<=size-1)&& (i>=3)){
 89             p->pNext = p2Head->pNext;
 90             p2Head->pNext = p;
 91         }
 92     }
 93 
 94     Print(p1Head);
 95     Print(p2Head);
 96     SNode* q = FindListFirstSameNode(p1Head,p2Head);
 97     cout<<q->value<<" "<<q->pNext<<endl;
 98     Destroy(p1Head);
 99     Destroy(p2Head);
100     return 0;
101 }