[LeetCode] 2. Add Two Numbers 

You are given two non-empty linked lists representing two non-negative integers. 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.You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

 

我的解法：肯定不能是全部取出来做加法运算再放回去了，一位一位运算

class Solution {public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {        ListNode *head = new ListNode(-1);        ListNode *r = head;            ListNode *p1 = l1;        ListNode *p2 = l2;        while(p1!=NULL && p2!=NULL){　　　　　　　　　　　　　　　　　　#两个链表都非空的情况            ListNode *p = new ListNode(p1->val + p2->val);             if(p->val >= 10){                p->val %= 10;                if(p1->next != NULL){　　　　　　　　　　　　　　　　　 #选择一个链表来进位                    p1->next->val += 1;                }else if(p2->next != NULL){                    p2->next->val += 1;                 }else{                    r->next = p;                                  #如果两个链表都不能进位了说明 1+9 这种情况，这一位放0，前面新增个结点，放1                    r=p;                    r->next = NULL;                    p = new ListNode(1);                }            }            r->next = p;            r=p;            r->next = NULL;            p1=p1->next ;            p2=p2->next ;        }        while(p1!=NULL){　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　#链表没有特殊情况时，可以接上直接退出            if(p1->val != 10){　　　　　　　　　　　　　　　　　　　　　　                r->next = p1;                break;            }else{                p1->val %= 10;　　　　　　　　　　　　　　　　　　　　　　　　　　 #如果这一位是10，那么要进位，进位又要考虑下一位是不是NULL了。如果是NULL，那么和上面一样，这一位置0，新增一个结点val=1，挂上去。OVER                ListNode *p = new ListNode(p1->val);                if(p1->next != NULL){                    p1->next->val += 1;                }else{                    r->next = p ;                    r=p;                    r->next = NULL;                    p = new ListNode(1);                }                r->next = p ;                r=p;                r->next = NULL;            }            p1=p1->next;        }        while(p2!=NULL){            if(p2->val != 10){                r->next = p2;                break;            }else{                p2->val %= 10;                ListNode *p = new ListNode(p2->val);                if(p2->next != NULL){                    p2->next->val += 1;                }else{                    r->next = p ;                    r=p;                    r->next = NULL;                    p = new ListNode(1);                }                r->next = p ;                r=p;                r->next = NULL;            }            p2=p2->next;        }        head = head->next ;　　　　　　　　　　　　　　　　　　　　　　　　　　　　#我不知道怎么不用头节点一个一个插入求出来的结果，只能先用尾插法建立链表，再让head = head —> next 了        return head;    }};

代码冗长，但好歹是我自己独立思考的结果，性能还可以，93%

 

下面放上大神代码，击败99% ，pointer to pointer ，还很简洁，看不懂，慢慢学习吧

class Solution {
     public:     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
                      // use a pointer to pointer to make appending to         // the end of the list easy -- Google: Linus "Good Taste"         // if you do not understand ListNode* node = nullptr; ListNode** nodeNext = &node; int carry = 0; while(l1 || l2 || carry) { int val1 = 0; int val2 = 0; if(l1) { val1 = l1->val; l1 = l1->next; } if(l2) { val2 = l2->val; l2 = l2->next; } int sum = val1 + val2 + carry; int val = sum % 10; carry = sum / 10; ListNode* newNode = new ListNode(val); *nodeNext = newNode; nodeNext = &(*nodeNext)->next; } return node; } };