链表相加详解程序员

给定两个链表，分别表示两个非负整数，他们的数字逆序存储在链表中，且每个节点只存储一个数字，计算两个数的和，并且返回和的链表头指针
如：输入：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 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 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

请按任意键继续. . .

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/7222.html