LeetCode编程题——add-two-numbers

题目描述

You are given two linked lists representing two non-negative numbers. 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.

题意：给出两个表示两个非负数的链表。这些数字以相反的顺序存储，每个节点都包含一个数字。添加两个数字并将其作为链表返回。

题目分析

我理解的题意是给出的链表的值都是非负数，如果两个数相加大于10 需要进位的话就向链表的后一个节点进位（这就是题目说的数字以相反的顺序存储），例如，输入是 (2 -> 4 -> 3) + (8 -> 6 -> 4) 那么输出应该是 0 -> 1 -> 8 ；因为2+8需要向下一个节点进 1 ，4+6+1=11 需要向下一个节点进1 ，最后一个节点位置为 3+4+1=8 。大致解题思路：

• 先考虑两个链表分别为空的情况——则直接返回另外一个链表；
• 当链表不为空时，设置一个临时变量temp存放两个链表的和值，再创建一个新的链表来存放输出链表，存放的值为temp%10
• 当链表1、链表2或temp不为0时进行循环，temp/=10
• 最后输出输出链表的值

代码实现

/**
 * 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) {
        //判断两个链表为空的情况
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        //至少有一个链表不为空
        int temp=0;
        ListNode *head=new ListNode(0);
        ListNode *p=head;
        while(l1 != NULL || l2 !=NULL || temp !=0)
        {
            if(l1 != NULL)
            {
                temp=temp+l1->val;
                l1=l1->next;
            }
            if(l2 != NULL)
            {
                temp=temp+l2->val;
                l2=l2->next;
            }
            p->next=new ListNode(temp%10);
            p=p->next;
            temp=temp/10;
        }
        return head->next;
    }
};