Add Two Numbers

文章目录

1. 1. Add Two Number
   1. 1.1. 题目
   2. 1.2. 思路
   3. 1.3. 解题

Add Two Number

题目

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.

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

Output:7 -> 0 -> 8

思路

两个链表l1和l2，设置一个新的链表来存储两个链表的和。从左往右进行运算，要设置一个进位flag。有四种情况：

1）l1和l2都不为空，sum=l1.val+l2.val+flag,新的链表对应的位置等于sum%10,进位flag更新为sum/10

2) l1不空，l2为空，sum=l1.val+flag,新的链表对应的位置等于sum%10,进位flag更新为sum/10

3) l1为空，l2不空，sum=l2.val+flag,新的链表对应的位置等于sum%10,进位flag更新为sum/10

4）l1和l2都为空,若flag为1，则新的链表末尾要新添一位。

解题

python版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # @return a ListNode
    def addTwoNumbers(self, l1, l2):
        dummy=ListNode(0)
        flag=0
        p=dummy
        while l1 and l2:
            sum=l1.val+l2.val+flag
            p.next=ListNode(sum%10)
            flag=sum/10
            l1=l1.next;l2=l2.next;p=p.next
        if l1:
            while l1:
                sum=l1.val+flag
                p.next=ListNode(sum%10)
                flag=sum/10
                l1=l1.next;p=p.next
        if l2:
            while l2:
                sum=l2.val+flag
                p.next=ListNode(sum%10)
                flag=sum/10
                l2=l2.next;p=p.next
        if flag==1:
            p.next=ListNode(1)
        return dummy.next

C++版

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */
 * 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 dummy(-1);
        int sum,flag=0;
        ListNode *p=&dummy;
        while(l1 and l2){
            sum=l1->val+l2->val+flag;
            p->next=new ListNode(sum%10);
            flag=sum/10;
            l1=l1->next;l2=l2->next;p=p->next;
        }
        while(l1){
            sum=l1->val+flag;
            p->next=new ListNode(sum%10);
            flag=sum/10;
            l1=l1->next;p=p->next;
        }
        while(l2){
            sum=l2->val+flag;
            p->next=new ListNode(sum%10);
            flag=sum/10;
            l2=l2->next;p=p->next;
        }
        if(flag)
            p->next=new ListNode(1);
        return dummy.next;
    }
};