链表相加详解程序员

给定两个链表，分别表示两个非负整数，他们的数字逆序存储在链表中，且每个节点只存储一个数字，计算两个数的和，并且返回和的链表头指针
如：输入：2-4-3，5-6-4   输出：7-0-8
因为两个数都是逆序存储，正好可以从头向后依次相加，完成“两个数的竖式计算”
pHead1:4-9-0-4-7-1
pHead2:1-7-1-5-5-4-2-8

pHead3:5-6-2-9-2-6-2-8

以下为实现代码：

#include<stdio.h> 
#include<stdlib.h> 
 
typedef struct Node{ 
	int data; 
	struct Node *next; 
}Node,*pNode; 
 
void print(pNode p){   //打印链表 
	while(p){ 
		printf("%d ",p->data); 
		p=p->next; 
	} 
	printf("/n"); 
} 
 
pNode Add(pNode pHead1,pNode pHead2){  //计算链表相加的值 
	pNode p1=pHead1->next; 
	pNode p2=pHead2->next; 
	pNode pCur; 
	pNode p3 = (pNode)malloc(sizeof(Node)); 
	p3->data=0; 
	p3->next =NULL; 
	int carry = 0;  //进位 
	int value = 0; 
	while(p1 && p2){ 
		value = p1->data + p2->data + carry; 
		carry = value/10; 
		value %= 10; 
		pCur=(pNode)malloc(sizeof(Node)); 
		pCur->data=value; 
		pCur->next=p3->next; 
		p3->next=pCur; 
		p1=p1->next; 
		p2=p2->next; 
	} 
	pNode p=p1 ? p1:p2; 
	while(p){        //计算较长的链表 
		value = p->data+carry; 
		carry /= 10; 
		value %= 10; 
		pCur=(pNode)malloc(sizeof(Node)); 
		pCur->data=p->data+carry; 
		pCur->next=p3->next; 
		p3->next=pCur; 
		p = p->next; 
	} 
	if(carry!=0){ 
		pCur=(pNode)malloc(sizeof(Node)); 
		pCur->data=carry; 
		pCur->next=p3->next; 
		p3->next=pCur; 
	} 
	return p3; 
} 
 
void destroy(pNode p){   //销毁链表 
	pNode temp=p; 
	while(p->next != NULL){ 
		temp=p->next; 
		p=temp->next; 
		free(temp); 
	} 
} 
 
int main(){ 
	int a[6]={1,7,4,0,9,4}; 
	int b[8]={8,2,4,5,5,1,7,1}; 
	pNode pHead1 = (pNode)malloc(sizeof(Node)); 
	pHead1->data = 0; 
	pHead1->next =NULL; 
	for(int i=0;i < 6;i++){ 
		pNode p=(pNode)malloc(sizeof(Node)); 
		p->data=a[i]; 
		p->next=pHead1->next; 
		pHead1->next=p; 
	} 
	pNode pHead2 = (pNode)malloc(sizeof(Node)); 
	pHead2->data = 0; 
	pHead2->next =NULL; 
	for(int j=0;j < 8;j++){ 
		pNode p=(pNode)malloc(sizeof(Node)); 
		p->data=b[j]; 
		p->next=pHead2->next; 
		pHead2->next=p; 
	} 
	print(pHead1->next); 
	print(pHead2->next); 
	pNode pHead3 = Add(pHead1,pHead2); 
	print(pHead3->next); 
	destroy(pHead1); 
	destroy(pHead2); 
	destroy(pHead3); 
	system("pause"); 
}

结果为：

4 9 0 4 7 1

1 7 1 5 5 4 2 8

8 2 6 2 9 2 6 5

请按任意键继续. . .