题目来源：https://leetcode.com/problems/add-two-numbers/
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
题目要求：给出两个链表l1和l2,将相对应的元素相加,如果产生进位则保留个位,相应的十位加在后面的对应元素上.
解体思路：
首先判断链表是否为空,若l1空,直接返回l2,相反返回l2
然后找到l1和l2链表最短的一个长度min_len,进入循环
循环过程中,为了减少空间的开销,可以将链表l1作为最终的结果链表,只需要改变l1的最大容量为l1+l2即可,另外相加过程中需要一个整型temp变量来保存进位.
循环结束之后,判断l1或l2空否(之前计算最短链表时可以做标记),然后将不空的链表中其他元素全部放入结果链表中即可.
提交代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/ class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
// ListNode *pResult = NULL;
// ListNode **pCur = &pResult; ListNode rootNode();
ListNode *pCurNode = &rootNode;
int a = ;
while (l1 || l2)
{
int v1 = (l1 ? l1->val : );
int v2 = (l2 ? l2->val : );
int temp = v1 + v2 + a;
a = temp / ;
ListNode *pNode = new ListNode((temp % ));
pCurNode->next = pNode;
pCurNode = pNode;
if (l1)
l1 = l1->next;
if (l2)
l2 = l2->next;
}
if (a > )
{
ListNode *pNode = new ListNode(a);
pCurNode->next = pNode;
}
return rootNode.next;
}
};
下面给出数组解决的代码,具体过程相同,只是数据存储结构不同：
#include <bits/stdc++.h>
#define MAX 1000010 using namespace std; int main()
{
int n1,n2;
while(~scanf("%d %d",&n1,&n2))
{
int *a=new int[n1+n2+];
int *b=new int[n2];
for(int i=;i<n1;i++)
scanf("%d",&a[i]);
for(int i=;i<n2;i++)
scanf("%d",&b[i]);
int minlen=min(n1,n2);
int maxlen=n1+n2-minlen;
int temp=;
for(int i=;i<minlen;i++)
{
a[i]=a[i]+b[i]+temp;
if(a[i]>=)
{
temp=a[i]/;
a[i]=a[i]%;
}
}
for(int j=minlen;j<maxlen;j++)
{
if(maxlen==n1)
a[j]=a[j];
else
a[j]=b[j];
}
for(int i=;i<maxlen;i++)
printf("%d ",a[i]);
printf("\n");
}
}