首页 > 代码库 > careercup-链表 2.5
careercup-链表 2.5
2.5 给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入： (7->1->6)+(5->9->2)，即617+295.
输出：2->1->9，即912.
进阶：
假设这些数位是正向存放的
示例：
输入：(6->1->7)+(2->9->5)，即617+295.
输出：9->1->2，即912.
逆向存放时，C++实现：
#include<iostream>#include<new>using namespace std;struct ListNode{ int val; ListNode *next; ListNode(int x):val(x),next(NULL) {}};void createList(ListNode *&L,int arr[],int n){ int i; ListNode *p=NULL; for(i=0; i<n; i++) { ListNode *tmp=new ListNode(arr[i]); if(L==NULL) { L=tmp; p=tmp; } else { p->next=tmp; p=tmp; } }}ListNode *merge(ListNode *L1,ListNode *L2){ if(L1==NULL&&L2==NULL) return NULL; if(L1==NULL||L2==NULL) return L1!=NULL?L1:L2; ListNode *p=L1; ListNode *pre=L1; ListNode *q=L2; int carry=0; while(p&&q) { int sum=p->val+q->val+carry; p->val=sum%10; carry=sum/10; pre=p; p=p->next; q=q->next; } while(p) { int sum=p->val+carry; cout<<sum<<endl; p->val=sum%10; carry=sum/10; pre=p; p=p->next; } ListNode *tmp=NULL; while(q) { int sum=q->val+carry; tmp=new ListNode(sum%10); carry=sum/10; pre->next=tmp; pre=tmp; q=q->next; } if(carry==1) { tmp=new ListNode(carry); pre->next=tmp; } return L1;}int main(){ ListNode *L1=NULL; ListNode *L2=NULL; int arr1[3]={7,1,9}; int arr2[5]={5,9}; createList(L1,arr1,3); createList(L2,arr2,2); ListNode *head=merge(L1,L2); ListNode *p=head; while(p) { cout<<p->val<<" "; p=p->next; } cout<<endl;}
正向存放时，可以先利用头插入将两个链表逆转，然后按照上面的过程求和。
careercup-链表 2.5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。