题干:

难度:Medium

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.

解析:

题意就是用链表模拟三位数加法,一个链表的顺序就是一个三位数从低位到高位的信息,题干中有不会包含leading zero的限定条件(比如对于数字9,链表长度为1,即(9),而不是(9->0->0)),我们可逐位对链表进行操作计算。

Java解法

/**
 * 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) {
        //sum和res都指向我们的答案链表,sum用于操作,res这最后提供链表入口
        ListNode sum=new ListNode(0);ListNode res=sum;
        //ifcar代表是否有进位,每次对同位对两数和ifcar求和,然后记录结果
        ListNode num1=l1;ListNode num2=l2;int num=0;int ifcar=0;
        //题目已经讲过不会有前置的0,即不满到三位的数链表长度不一定为3
        //所以要对相关位数是否存在做判断
        while(num1!=null || num2!=null || ifcar!=0){
            int n1,n2;
            if (num1==null)
                n1=0;
            else
                n1=num1.val;
            if (num2==null)
                n2=0;
            else
                n2=num2.val;
            num=(n1+n2+ifcar)%10;
            //如果对下一位还有进位,ifcar=1,否则这次计算完后就应该置零
            if ((n1+n2+ifcar)/10==1)
                ifcar=1;
            else
                ifcar=0;
            sum.next=new ListNode(num);
            sum=sum.next;
            if(num1!=null)
                num1=num1.next;
            if(num2!=null)
             num2=num2.next;
        }
    //返回结果链表
    return res.next;
    }
}

Pyhon解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        #思路相同,relist,res都指向结果链表
        relist=ListNode(0)
        res=relist
        #ifcar用于判断是否有进位 
        num1=l1
        num2=l2
        ifcar=0
        while num1!=None or num2!=None or ifcar!=0:
            if num1==None:
                n1=0
            else:
                n1=num1.val
            if  num2==None:
                n2=0
            else:
                n2=num2.val
            num=(n1+n2+ifcar)%10
            #判断ifcar应为1还是0
            if (n1+n2+ifcar)//10==1:
                ifcar=1
            else:
                ifcar=0
            
            relist.next=ListNode(num)
            relist=relist.next
            if num1!=None:
                num1=num1.next
            if num2!=None:
                num2=num2.next
                
        return res.next
最后修改:2020 年 01 月 22 日 05 : 53 PM