leetcode:2.两数相加

电玩女神 2022-03-11 04:08 185阅读 0赞

### 题目描述： ###

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

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

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

##### 示例： #####

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

##### 题目难度：中等 #####

##### 分析： #####

属于链表题目的常规操作，并且题目原型已经给了链表部分的代码。这里要注意的是head是个位数，这样从head开始遍历的时候逐步相加就可以了，无疑简化了题目，只需要遍历两个链表，然后注意超过10以后进位就可以了。代码如下：

###### 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) { 
        	// 首先定义一个结果链表作为最后的返回值
            ListNode res = new ListNode(0);
            // 定义p，q分别指向l1，l2
            ListNode p = l1, q = l2, curr = res;
            // 进位标识，初始化为0
            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;
                // 因为超过10进位，所以 / 10 就可以知道下一次进位是多少了
                carry = sum / 10;
                // 把sum取余得到具体数字并加入当前链表中（比如15 % 10 = 5，因此写5进1）
                curr.next = new ListNode(sum % 10);
                // 指向下一位
                curr = curr.next;
                if (p != null) p = p.next;
                if (q != null) q = q.next;
            }
            if (carry > 0) { 
            	// 当循环完以后如果进位大于0说明还需要添加一位
                curr.next = new ListNode(carry);
            }
            // 最后返回链表
            return res.next;
        }
    }

###### python: ######

# 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:
            res = ListNode(0)
            p, q, curr, carry = l1, l2, res, 0
            while p != None or q != None:
                x = p.val if p != None else 0
                y = q.val if q != None else 0
                temp = x + y + carry
                carry = temp // 10
                curr.next = ListNode(temp % 10)
                if p != None:
                    p = p.next
                if q != None:
                    q = q.next
                curr = curr.next
            if carry > 0:
                curr.next = ListNode(carry)
            return res.next

##### 总结： #####

可以看出不管是`java`还是`python`思路都一样，语言只是工具。时间复杂度为 O ( m a x ( m , n ) ) O(max(m, n)) O(max(m,n))， 因为遍历链表的时候，可能长短不一样，所以需要遍历的次数应该以长的为准。最后leetcode给出了一个扩展：就是顺序颠倒过来，如下：

(3→4→2)+(4→6→5)=8→0→7

这样的话难度会稍微大点，感兴趣的同学可以尝试下。