LeetCode #2 Add Two Numbers 双链归并 链表

Description

---

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.　

思路

---

　　这是一个用链表处理大数相加的问题，我首先联想到的就是之前做过的多项式相加，本题不过是 low 版本的多项式相加问题。处理的思路很类似，先将第一个链表和第一个链表的相同位数的数字相加，将相加的值存储到第三个链表上。当其中一个链表已经遍历完而另一个链表还有未遍历完的时候，就将未遍历完的数字存储到第三个链表上即可。最后将第三个链表遍历一遍，处理数字满十进一位的情况。我这个方法可能有些暴力，如果你有更好的方法，欢迎指点。

//Runtime: 45 ms
/**
 * 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) {
        ListNode *p1, *p2, *p3, *t3, *l3Head;
        p1 = l1;
        p2 = l2;
        l3Head = NULL;
        while((p1!=NULL) && (p2!=NULL)) {
            p3 = new ListNode(p1->val + p2->val);
            p1 = p1->next;
            p2 = p2->next;
            if(l3Head == NULL) {
                t3 = l3Head = p3;
            }
            else{
                t3->next = p3;
                t3 = p3;
            }
        }
        while(p1 != NULL) {
            p3 = new ListNode(p1->val);
            t3->next = p3;
            t3 = p3;
            p1 = p1->next;
        }
        while(p2 != NULL) {
            p3 = new ListNode(p2->val);
            t3->next = p3;
            t3 = p3;
            p2 = p2->next;
        }
        
        p3 = l3Head;         
        while(p3 != NULL) {
            if(p3->val >= 10) {
                p3->val = p3->val % 10;
                if(p3->next == NULL) {
                    p3->next = new ListNode(1);
                }
                else {
                   p3->next->val = p3->next->val + 1;
                }
            }
            p3 = p3->next;
        }
        
        return l3Head;
    }
};