leetcode: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

Hide Tags

Linked List Math

Show Similar Problems

　　这是一道简单的链表操作实现高精度整数相加，奈何习惯了国内POJ在线编程详细的中文问题描述和输入输出sample，至少前两遍提交根本没有完全看懂题意，所以一定要提高英文阅读量，简单说说高精度整数相加算法，就是从链表头遍历到表尾，需要注意两个number可能位数不一样长，还有最后一次加操作结束后不要忘了进位。（扯点闲话，非常欣赏leetcode这种在线提交的风格，不同于ACM竞赛之类需要完整的考虑输入输出，在这里就像笔试现场，面试官等着你提交手写的代码，只要认真研究核心的算法就行了，上代码…………）

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         ListNode *p1,*p2,*p3,*l3,*node;
13         int add,temp;
14         
15         p1 = l1;
16         p2 = l2;
17         add = temp = 0;
18         node = new ListNode(0);
19         temp += p1->val + p2->val;
20         if(temp>=10)
21         {temp = temp-10;add++;}
22         node->val = temp;
23         l3 = p3 = node;
24         p1 = p1->next;
25         p2 = p2->next;
26         while(p1!=NULL || p2!= NULL)
27         {
28             temp = add;
29             if(p1!=NULL) temp += p1->val;
30             if(p2!=NULL) temp += p2->val;
31             if(temp>=10)
32             {
33                 p3->next = new ListNode(temp-10); 
34                 add=1;
35             }
36             else{
37                 p3->next = new ListNode(temp); 
38                 add=0;
39             }
40             if(p1!= NULL) p1 = p1->next;
41             if(p2!= NULL) p2 = p2->next;
42             p3 = p3->next;
43         }
44         if(add)
45         {
46             p3->next = new ListNode(add);
47         }
48        return l3;
49     }
50 };