Problem: 2. 两数相加
思路
主要是一一相加和逆序的方式存储
先说逆序储存，看下图
我们先声明出指针p和指针q，还有指针head（主要用于return上而已），然后进行一系列操作，之后，p = q，之后的操作就是对q进行，至于p，只做一个动作，p = q
int flag = 0;
struct ListNode *p = NULL, *q = NULL, *head = NULL;
while(l1 != NULL && l2 != NULL) {
if(flag == 0) {
flag = 1;
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->next = NULL;
head = p;
} else {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->next = NULL;
p->next = q;
p = q;
}
l1 = l1->next;
l2 = l2->next;
}
至于相加嘛！好说，将对应的两个数加起来，然后检查是否大于9，如果是，则要保留个位，并进一位（也就是将十位数的部分放入下一个相加的过程中），以指针p的部分为例——指针q的部分也一样。
p->val = l1->val + l2->val;
if(p->val > 9) {
last = p->val / 10;
p->val %= 10;
} else last = 0;
但是，要知道，l1与l2终会到达null，所以，对于剩余的部分也只是解决前面的“进一位”遗留的问题而已.
while(l1 != NULL) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = l1->val + last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
l1 = l1->next;
}
while(l2 != NULL) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = l2->val + last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
l2 = l2->next;
}
到最后，倘若还存在进一位，就得要再建一个节点。
if(last > 0) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
}
解题方法
由思路可知
Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *p = NULL, *q = NULL, *head = NULL;
int flag = 0, last;
while(l1 != NULL && l2 != NULL) {
if(flag == 0) {
flag = 1;
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val = l1->val + l2->val;
if(p->val > 9) {
last = p->val / 10;
p->val %= 10;
} else last = 0;
p->next = NULL;
head = p;
} else {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = l1->val + l2->val + last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
}
l1 = l1->next;
l2 = l2->next;
}
while(l1 != NULL) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = l1->val + last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
l1 = l1->next;
}
while(l2 != NULL) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = l2->val + last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
l2 = l2->next;
}
if(last > 0) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = last;
if(q->val > 9) {
last = q->val / 10;
q->val %= 10;
} else last = 0;
q->next =NULL;
p->next = q;
p = q;
}
return head;
}
一些感想
其实，当时在解决这道题的时候，碰到过这样的问题
Line 70: Char 15: runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct ListNode', which requires 8 byte alignment [ListNode.c]0xbebebebebebebebe: note: pointer points here<memory cannot be printed>
后来，在我看了AuthurLEE的文章之后，我才知道原来是忘记在初始化的时候，让指针指向NULL了（包括head指针，还有结构体里面的next）
