链表系列之单链表——使用单链表实现大整数相加

大数相加在我之前的一篇博客里有一个使用数组实现的方案，使用单链表实现更灵活。

有两个由单链表表示的数。每个结点代表其中的一位数字。

eg.

?Input:(3->9->6),(4->7->8->3)

Output:(7->6->5->4)

#include <iostream>
#include <stack>
using namespace std;

typedef struct node
{
	int data;
	node *next;
}Node,*LinkList;
//建立链表
Node* createList(const int a[],int n)
{
	Node *head,*endPtr;
	head = endPtr = NULL;
	
	for(int i=0;i<n;i++)
	{
		Node *temp = new Node;
		temp->data = a[i];
		temp->next = NULL;

		if(i==0)
		{
			head = endPtr = temp;
		}
		else
		{
			endPtr->next = temp;
			endPtr = temp;
		}
	}

	return head;
}
/*从尾到头打印链表，要求不修改链表结构*/
//使用栈适配器
void PrintListReversing(LinkList pHead)
{
	stack<Node*> nodes;
	Node* pNode = pHead;
	
	if(pNode==NULL)
		return;

	while(pNode!=NULL)   //将节点依次入栈
	{
		nodes.push(pNode);
		pNode = pNode->next;
	}

	while(!nodes.empty())   //出栈
	{
		pNode = nodes.top();   //读取栈顶元素
		cout<<pNode->data;
		nodes.pop();   //删除栈顶元素
	}
}
//大数相加
Node *ListAdd(Node* L1,Node* L2)
{
	if(L1==NULL)
		return L2;
	if(L2==NULL)
		return L1;

	Node *ptr1 = L1,*ptr2 = L2,*ResultPtr=NULL,*TmpPtr=NULL;
	int carry = 0;

	Node *p_node = new Node();
	p_node->data = (L1->data+L2->data)%10;
	p_node->next = NULL;
	carry = (L1->data+L2->data)/10;
	ResultPtr = TmpPtr = p_node;
	TmpPtr->next = NULL;
	L1 = L1->next;
	L2 = L2->next;

	while(L1 && L2)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		int tmp = L1->data+L2->data+carry;
		carry = tmp/10;
		pNode->data = tmp%10;
		pNode->next = NULL;

		TmpPtr = TmpPtr->next;
		L1 = L1->next;
		L2 = L2->next;
	}

	while(L1)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		int tmp = L1->data+carry;
		carry = tmp/10;
		pNode->data = tmp%10;
		pNode->next = NULL;

		TmpPtr = TmpPtr->next;
		L1 = L1->next;
	}
	while(L2)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		int tmp = L2->data+carry;
		carry = tmp/10;
		pNode->data = tmp%10;
		pNode->next = NULL;

		TmpPtr = TmpPtr->next;
		L2 = L2->next;
	}

	if(carry)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		pNode->data = carry;
		pNode->next = NULL;
	}

	return ResultPtr;
}

int main()
{
	int a[] = {1,9,9};  //991
	int b[] = {9,8,5,6,2,8};   //8266589
	Node *L1 = createList(a,3),*L2 = createList(b,7),*L3 = NULL;

	L3 = ListAdd(L1,L2);

	PrintListReversing(L1);
	cout<<"+";
	PrintListReversing(L2);
	cout<<"=";
	PrintListReversing(L3);
	cout<<endl;

	return 1;
}