题目

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.

解答

这题的长相就是很容易让人想到链表数据结构的应用

然鹅，笔者好久没有用C++写结构体了，主要时间不是用来写算法，而是用来创建链表hh~

解题思路：

数据输入后，题干说是非空的链表，故不用判断链表是否为空

这个方法有一点像高精度加法的感觉，最重要的是进位如何处理。

并且算法是对应位置元素相加，所以两个指针最好同时移动，但是由于两个链表长度可能相等，也可能不相等

需要注意这些情况

• 若链表1和链表2长度相等，则指向两个链表的指针同时后移，到next

每次相加后都记下进位的变化，进位数累加到下一次相加操作。

若相加完成之后进位为0，就是可以直接出结果啦！

若是进位数为1，则结果链表还需要再新增一个链表node存下来，可不能丢了！

• 若链表1和链表2长度不相等，则指向两个链表的指针同时后移，直到那个短的链表已经遍历结束为止

此时指向短链表的指针已经到头了，就不用往下遍历了，但是指向长链表的指针还要和进位数相加，继续遍历，

直到长链表的指针也指向空，且进位数也妥善的被处理之后，循环结束。

判断循环结束的条件
while(p!=NULL || q!=NULL || carry != 0)

笔者的输入测试用例的格式是：

一行一个数
结束输入使用q

如图操作：

Add2Num.png

#include <iostream>
#include <cstdio>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
        //不带头节点的尾插法
    ListNode *createList()
    {
        ListNode *pHead = NULL;
        ListNode *p = pHead;
        char x;
        while(cin>>x)
        {
            if(x == 'q')
            {
                break;
            }
            
            int value = x - '0';
            ListNode *pNew = new ListNode(value);
            pNew->next = NULL;
            
            if(pHead == NULL)
            {
                pHead = pNew;
            }
            else
            {
                p->next = pNew;
            }
            p = pNew;

        }
        
        return pHead;
    }
     
        //循环打印链表
    void displayList(ListNode *head)
    {

        ListNode *p = head;
        while(p != NULL)
        {
            cout<<p->val<<"->";
            p = p->next;
        }
        cout<<"NULL"<<endl;
    }
    
     //解题主体
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0; //进位记录
        ListNode *p,*q;//指针p，q分别指向两个链表
        p = l1;
        q = l2;
        ListNode *result = NULL;
        ListNode *pResult = result;
        while(p!=NULL || q!=NULL || carry != 0) //结束循环的条件 很重要！！！
        {
            int add;
            if (p != NULL && q != NULL)
            {
                add = p->val + q->val + carry;
                p = p->next;
                q = q->next;
            }
            else if (p == NULL && q != NULL)
            {
                add = 0 + q->val + carry;
                q = q->next;
            }
            else if (p != NULL && q == NULL)
            {
                add = p->val + 0 + carry;
                p = p->next;
            }
            else
            {
                add = 0 + 0 + carry;
            }
            
            
            int number = add % 10;
            carry = add / 10;
            
            ListNode *pNew = new ListNode(number);
            pNew->next = NULL;
            
            if(result == NULL)
            {
                result = pNew;
            }
            else
            {
                pResult->next = pNew;
            }
            pResult = pNew;
        }
        
        return result;
    }
};

int main()
{
    Solution s;
    ListNode *l1,*l2,*result;
    l1 = s.createList();
    s.displayList(l1);
    l2 = s.createList();
    s.displayList(l2);
    result = s.addTwoNumbers(l1,l2);
    s.displayList(result);
    
    return 0;
}