美文网首页
2. 两数相加(中等,链表)

2. 两数相加(中等,链表)

作者: Magina敌法师 | 来源:发表于2019-05-22 16:14 被阅读0次

    中文版本

    题目

    难度:中等

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

    如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

    您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

    示例:

    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807

    解题思路

    这题比较简单,直接用进位法做就可以了,但是边界条件还需要考虑清楚:

    • 当一个列表比另一个列表长时

    l1=[0,1],l2=[0,1,2],l2=[0,1,2]

    • 当一个列表为空时,即出现空列表

    l1=[],l2=[0,1],l2=[0,1]

    • 求和运算最后可能出现额外的进位,这一点很容易被遗忘

    l1=[9,9],l2=[1],l2=[1]

    代码

    Python3

    # 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:
            dummy_head = ListNode(0)
            curr = dummy_head
            carry = 0
            
            while l1 is not None or l2 is not None:
                    
                val1 = l1.val if l1 is not None else 0
                val2 = l2.val if l2 is not None else 0
    
                sum = carry + val1 + val2
                curr.next = ListNode(sum % 10)
                curr = curr.next
    
                carry = 0 if sum < 10 else 1
                
                l1 = l1.next if l1 is not None else None
                l2 = l2.next if l2 is not None else None
                
            if carry > 0:
                curr.next = ListNode(carry)
                
            return dummy_head.next
    

    Java

    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;
    }
    

    Go

    func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
        dummyHead := &ListNode{0, nil}
        p, q, curr := l1, l2, dummyHead
        carry := 0
        for p != nil || q != nil {
            var x, y int
            if p != nil {
                x = p.Val
            } else {
                x = 0
            }
            if q != nil {
                y = q.Val
            } else {
                y = 0
            }
            sum := x + y + carry
            curr.Next = &ListNode{sum % 10, nil}
            curr = curr.Next
            if p != nil {
                p = p.Next
            } else {
                p = nil
            }
            if q != nil {
                q = q.Next
            } else {
                q = nil
            }
            if sum >= 10 {
                carry = 1
            } else {
                carry = 0
            }
        }
        if carry == 1 {
            curr.Next = &ListNode{1, nil}
        }
        return dummyHead.Next
    }
    

    相关文章

      网友评论

          本文标题:2. 两数相加(中等,链表)

          本文链接:https://www.haomeiwen.com/subject/ivsuzqtx.html