😐 LeetCode 2. 两数相加 [链表] - 永雏多氢菲の書库

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1:

输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [7,0,8]，即 342 + 465 = 807

示例 2:

输入: l1 = [2,4,3], l2 = [2,4,3]
输出: [0]

示例 3:

输入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出: [8,9,9,9,0,0,0,1]

思路#

链表是逆序存的，head 处对应的就是个位数
需要返回的是一个新链表，首先对个位数求和，将其结果作为新链表的 head
在求和时用一个变量 i 存储进位，进位非 0 即 1
当 l1 和 l2 长度相同时，同时进行遍历，求和结果加上进位后 mod 10
当 l1 和 l2 长度不相同时，有一方遍历结束后，单独遍历另一方
最后检查进位是否计算完毕，否则的话创建一个新的 val = 1 的节点接在循环结束的 node 后，返回个位数求和得到的 head 即可

题解#

1. python#

1
class Listnode:
2
    def __init__(self, val=0, next=None):
3
        self.val = val
4
        self.next = next
5

6
class Solution:
7
    @staticmethod
8
    def addTwoNum(l1: Listnode, l2: Listnode):
9
        # 当前指针在 head 处，处理的是个位的和
10
        node1 = Listnode((l1.val + l2.val) % 10)
11
        i = (l1.val + l2.val) % 10
12
        # 处理完个位后得到一个节点，用于指向后续计算结果
13
        node = node1
14
        if l1.next != None and l2.next != None:
15
            while l1.next and l2.next:
16
                # 十位的和要加上上一次的进位 i
17
                node.next = Listnode((l1.next.val + l2.next.val + i) % 10)
18
                i = (l1.next.val + l2.next.val + i) % 10
19
                l1 = l1.next
20
                l2 = l2.next
21
                node = node.next
22
        if l1.next != None:
23
            while l1.next:
24
                node.next = Listnode((l1.next.val + i) % 10)
25
                i = (l1.next.val + i) % 10
26
                l1 = l1.next
27
                node = node.next
28
        if l2.next != None:
29
            while l2.next:
30
                node.next = Listnode((l2.next.val + i) % 10)
31
                i = (l2.next.val + i) % 10
32
                l2 = l2.next
33
                node = node.next
34
        # 如果多出来一个进位， i 仍为 1
35
        if i == 1:
36
            node.next = Listnode(1)
37
        return node1
38

39
    @staticmethod
40
    def print_linked_list(head):
41
        while head:
42
            print(head.val, end=" → ")
43
            head = head.next
44
        print("None")

2. java#

1
public class Solution {
2
    static ListNode addTwoNum(ListNode l1, ListNode l2) {
3
        ListNode head = null, tail = null;
4
        int i = 0;
5
        while (l1 != null || l2 != null) {
6
            int n1 = l1 != null ? l1.val : 0;
7
            int n2 = l2 != null ? l2.val : 0;
8
            int sum = n1 + n2 + i;
9
            // 第一次 head 为 null
10
            if (head == null) {
11
                head = tail = new ListNode(sum % 10);
12
            } else {
13
                tail.next = new ListNode(sum % 10);
14
                tail = tail.next;
15
            }
16
            i = sum % 10;
17
            if (l1.next != null) l1 = l1.next;
18
            if (l2.next != null) l2 = l2.next;
19
        }
20
        if (i > 0) tail.next = new ListNode(i);
21
        return head;
22
    }
23
}

思路#

题解#

1. python#

2. java#

Comments

Music

Table of Contents