[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.

这题说是2->4->3和5->6->4组成两个多位数342和465相加，把和807再写成7->0->8
其实仔细想想并不需要求出342和465来，直接就可以在链表上进行操作
2+5=7,4+6=10-10=0(有进位要求),2+5+1=8

有点类似归并排序的合并过程，两个链表同时取出一个数来相加，超过十就进位，
直到较短的链表取完，再把较长链表的后半部分直接接上去就行，依然要注意进位

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list=new ListNode(0);
        ListNode res=list; 
        int target=0,sum=0;
        while(l1!=null&&l2!=null){
            sum=l1.val+l2.val+target;
            if(sum>9){
                sum=sum-10;
                target=1;
            }else{
            target=0;
                }
            
            list.next=new ListNode(sum);
            l1=l1.next;
            l2=l2.next;
            list=list.next;
        }
        while(l1!=null){
            sum=l1.val+target;
            if(sum>9){
                sum=sum-10;
                target=1;
            }else{
                target=0;
            }
            
            list.next=new ListNode(sum);
            l1=l1.next;
            list=list.next;
        }
        while(l2!=null){
            sum=l2.val+target;
            if(sum>9){
                sum=sum-10;
                target=1;
            }else{
                target=0;
            }
            
            list.next=new ListNode(sum);
            l2=l2.next;
            list=list.next;
        }
        if (target!=0){
            list.next=new ListNode(target);
        }
        return res.next;
    }
}

上面是比较易懂的版本，下面简化一下多个while的操作

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

python解法类似

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        re = ListNode(0)
        r=re
        carry=0
        while(l1 or l2):
            x= l1.val if l1 else 0
            y= l2.val if l2 else 0
            s=carry+x+y
            carry=s//10
            r.next=ListNode(s%10)
            r=r.next
            if(l1!=None):l1=l1.next
            if(l2!=None):l2=l2.next
        if(carry>0):
            r.next=ListNode(1)
        return re.next

最后编辑于：2018.12.21 20:52:50