笔试题目：
1、用单向链表表示十进制整数，求两个正整数的和。如下图，1234+34=1268， 注意:单向链表的方向，不允许使用其他的数据结构。
题目分析：
题目中提到了，数据结构只能使用单链表，所以数组不在考虑范围之内。 因为将数字转为单链表以后，最高位排在表头，而我们进行整数加法的时候，是从个位开始的，与单链表的顺序相反。所以我们考虑对链表进行反转，然后再做加法。
其中反转和求和的示意图如下：
对求和以后的结果再进行反转：
下面是C++的实现
代码解读
1.节点的数据结构定义如下:
//节点定义
struct Node_t
{
int m_value;
Node_t * m_pNext;
};
2. 将int转为List
//int转List
Node_t* IntToNodeList(int value)
{
Node_t* pHead= new Node_t;
pHead->m_pNext=nullptr;
while(value > 0)
{
Node_t * pNewNode = new Node_t;
pNewNode->m_value = value % 10;
pNewNode->m_pNext = pHead->m_pNext;
pHead->m_pNext = pNewNode;
value = value / 10;
}
Node_t * pResult = pHead->m_pNext;
pHead->m_pNext=nullptr;
delete pHead;
return pResult;
}
3.将List转为int
//List转int
int NodeListToInt(Node_t* pList)
{
Node_t * pHead = pList;
int nResult = 0;
while(( pHead != nullptr)){
nResult = nResult*10+pHead->m_value;
pHead = pHead->m_pNext;
}
return nResult;
}
4. 释放节点内存
//释放节点
void FreeNodeList(Node_t* pList)
{
Node_t* pHead = pList;
Node_t* pFree = nullptr;
while(pHead)
{
pFree = pHead;
pHead = pHead->m_pNext;
delete pFree;
}
}
5 .实现链表的反转
//链表翻转,使用传入的链表的内存
Node_t* ReverseList(Node_t* pList)
{
Node_t * pResult = nullptr;
Node_t * pTem = nullptr;
while(pList != nullptr)
{
pTem = pList->m_pNext;
pList->m_pNext=pResult;
pResult= pList;
pList = pTem;
}
return pResult;
}
6.将链表相加
//链表相加
Node_t * AddList(Node_t* pLeft,Node_t* pRight)
{
Node_t * pRevLeft = ReverseList(pLeft);
Node_t * pRevRight = ReverseList(pRight);
Node_t * pResult=nullptr;
int toUpValue = 0;//进位
int nLeftValue = 0;
int nRightValue = 0;
while(pRevLeft != nullptr || pRevRight != nullptr)
{
Node_t * pNewNode = new Node_t;
pNewNode->m_pNext = pResult;
pResult = pNewNode;
nRightValue = 0;
nLeftValue = 0;
if(pRevLeft)
{
nLeftValue = pRevLeft->m_value;
pRevLeft = pRevLeft->m_pNext;
}
if(pRevRight)
{
nRightValue = pRevRight->m_value;
pRevRight = pRevRight->m_pNext;
}
int curPosSum = nRightValue+nLeftValue;
pNewNode->m_value = curPosSum+toUpValue;
toUpValue = curPosSum/10;
}
return pResult;
}
主函数：
int main(int argc,char * argv[])
{
int nLeftValue = rand();
int nRightValue = rand();
std::cout<<"Test Reverst"<<std::endl;
Node_t * pLeftList = IntToNodeList(nLeftValue);
Node_t * pRightList = IntToNodeList(nRightValue);
Node_t * pSumList = AddList(pLeftList,pRightList);
int nSum = NodeListToInt(pSumList);
FreeNodeList(pLeftList);
FreeNodeList(pRightList);
FreeNodeList(pSumList);
std::cout<<"TEST "<<nRightValue<<" "<<nLeftValue <<" "<<nSum<<std::endl;
return 0;
}
转载于:https://www.cnblogs.com/Dennis-mi/p/10326643.html
相关资源：单链表的逆转求和
