leetcode 2 Add Two Numbers
z
 2019-04-09 10:36:27  

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse orderand 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:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import utils.ListNode;

public class addTwoNumbers {
  public ListNode addTwoNumbers(ListNode a, ListNode b) {
    ListNode ans = new ListNode(0);
    ListNode head = ans;
    int carry = 0;
    while (a.next!= null && b.next != null) {
      int t = (a.val + b.val + carry)%10;
      carry = t/10;
      ListNode tt = new ListNode(t);
      head.next = tt;
      head = head.next;
    }
    while (a.next != null) {
      int t = (a.val + carry)%10;
      carry = t/10;
      ListNode tt = new ListNode(t);
      head.next = tt;
      head = head.next;
    }
    while (b.next != null) {
      int t = (b.val + carry)%10;
      carry = t/10;
      ListNode tt = new ListNode(t);
      head.next = tt;
      head = head.next;
    }
    if (carry != 0) {
      ListNode t = new ListNode(carry);
      head.next = t;
    }
    return ans.next;
  }
}

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

  • 最直接的方法是利用reverse，先转换为上述的问题，得到结果后再reverse回来

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            a = self.reverse(l1)
            b = self.reverse(l2)
            
            dump = ListNode(0)
            p = dump
            carry = 0
            while a and b:
                t = (a.val + b.val + carry) % 10
                cur = ListNode(t)
                p.next = cur
                p = p.next
                carry = (a.val + b.val + carry)/10
                a = a.next
                b = b.next
            while a:
                t = (a.val + carry) % 10
                cur = ListNode(t)
                carry = (a.val + carry)/10
                p.next = cur
                p = p.next
                a = a.next
            while b:
                t = (b.val + carry) % 10
                cur = ListNode(t)
                carry = (b.val + carry)/10
                p.next = cur
                p = p.next
                b = b.next
            if carry:
                cur = ListNode(carry)
                p.next = cur
                p = p.next
            return self.reverse(dump.next)
                
            
        def reverse(self, head):
            pre = None
            p = head
            while p is not None:
                q = p.next
                p.next = pre
                pre = p
                p = q
            return pre

  • 但是题目要求不用reverse，这样一来，直接得出l1和l2对应的整数，将其相加后变成列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        a = self.getNumber(l1)
        b = self.getNumber(l2)
        c = a + b
        return self.getLinkList(c)
        
    
    def getNumber(self, l):
        val = 0
        while l:
            val = val*10 + l.val
            l = l.next
        return val
    
    def getLinkList(self, val):
        if val == 0:
            return ListNode(0)
        dump = ListNode(0)
        while val:
            y = val % 10
            val = val / 10
            # dump.next, dump.next.next = ListNode(y), dump.next
            t = dump.next
            dump.next = ListNode(y)
            dump.next.next = t
        return dump.next