Google : Link addition

add 2 link lists without reverse in O(n) n constant space

eg
1-2-3 + 1-7
1-4-0

当然是用递归，不过程序写出来需要一些小技巧地：

1. 
   
2. struct NODE
   
3. {
   
4.         int nVal;
   
5.         NODE* pNext;
   
6. 
   
7.         NODE(int n) : nVal(n), pNext(NULL) {}
   
8. };
   
9. 
   
10. int GetLen(NODE* pHead)
    
11. {
    
12.         int nRet = 0;
    
13. 
    
14.         while (NULL != pHead)
    
15.         {
    
16.                 nRet++;
    
17.                 pHead = pHead->pNext;
    
18.         }
    
19. 
    
20.         return nRet;
    
21. }
    
22. 
    
23. NODE* CalcAdd(NODE* p1, int n, NODE* p2, int m)
    
24. {
    
25.         if (0 == n || 0 == m)
    
26.                 return NULL;
    
27. 
    
28.         NODE* pNode = NULL;
    
29.         NODE* pRet = NULL;
    
30. 
    
31.         if (m != n)
    
32.         {
    
33.                 if (n > m)
    
34.                 {
    
35.                         pRet = CalcAdd(p1->pNext, n-1, p2, m);
    
36.                         pNode = new NODE(p1->nVal);
    
37.                 }
    
38.                 else
    
39.                 {
    
40.                         pRet = CalcAdd(p1, n, p2->pNext, m-1);
    
41.                         pNode = new NODE(p2->nVal);
    
42.                 }
    
43.         }
    
44.         else
    
45.         {
    
46.                 pRet = CalcAdd(p1->pNext, n-1, p2->pNext, m-1);
    
47.                 pNode = new NODE(p1->nVal + p2->nVal);
    
48.         }
    
49. 
    
50.         if (pRet != NULL && pRet->nVal >= 10)
    
51.         {
    
52.                 pRet->nVal = pRet->nVal%10;
    
53.                 pNode->nVal++;
    
54.         }
    
55.         pNode->pNext = pRet;
    
56. 
    
57.         return pNode;
    
58. }
    
59. 
    
60. NODE* AddLnk(NODE* p1, NODE* p2)
    
61. {
    
62.         assert(p1 && p2);
    
63. 
    
64.         NODE* pHead = CalcAdd(p1, GetLen(p1), p2, GetLen(p2));
    
65.         if (pHead->nVal >= 10)
    
66.         {
    
67.                 NODE* pTmp = pHead;
    
68.                 pHead = new NODE(1);
    
69.                 pTmp->nVal = pTmp->nVal%10;
    
70.                 pHead->pNext = pTmp;
    
71.         }
    
72. 
    
73.         return pHead;
    
74. }
    

复制代码