LeetCode Add Two Numbersの2つの数を加算
7975 ワード
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 *creatnode(int a){
12 ListNode *nod=new ListNode(a);
13 nod->next=0;
14 return nod;
15 }
16 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
17 if(l1==0) return l2;
18 if(l2==0) return l1;
19 struct ListNode *p=l1,*c=0;
20 int tem=0,s=0;
21 while(l1!=0&&l2!=0){ //
22 tem=l1->val+l2->val+tem;
23 s=tem%10; //
24 tem=tem/10; //
25 l1->val=s;
26 if(l1->next==0)
27 c=l1;
28 l1=l1->next;
29 l2=l2->next;
30 }
31 if(l1!=0&&l2==0||l1==0&&l2!=0){
32 if(l1==0&&l2!=0){
33 c->next=l2;
34 l1=c->next;
35 }
36 if(tem==0)
37 return p;
38 while(l1!=0){
39 tem=l1->val+tem;
40 l1->val=tem%10;
41 tem=tem/10;
42 if(l1->next==0)
43 c=l1;
44 l1=l1->next; //l1 NULL
45 }
46 if(tem!=0)
47 c->next=creatnode(tem);
48 }
49 else if(l1==0&&l2==0&&tem!=0){
50 c->next=creatnode(tem);
51 }
52 return p;
53 }
54 };
題意:2つの10進数は、逆方向に一方向チェーンテーブルに格納され、各ビット数が1つのノードを占めています.和を求めるチェーンテーブル.
考え方:提供された最初のチェーンテーブルを返す結果として、加算された結果がこのチェーンテーブルに存在します.l 1がl 2より長い場合、結果はl 1を保存しても問題ない.l 2がl 1より長い場合、l 2がl 1より多い要素をl 1の後ろに追加することで、ノードをあまり作成する必要がなくなります.チェーンテーブル長とはまったく関係ありません.
注意:2つのチェーンテーブルの等長と非等長を考慮すると、1+9999,0+0のような状況が発生する可能性があります.
ツッコミ:まずメモリを節約する方法で、コードが長すぎるような気がします.コード量を減らしたものを書き直した結果、メモリが制限を超えた.メモリを節約する方法を再改善します.実際には、加算に関数をもう1つ書くと、コード量が少なくなります.このコードは他の人より少し長いです~