動機

linked list是不是與長度,reverse很有緣

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]Output: [0]

 

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

 

Follow up: Could you solve it without reversing the input lists?

Sol

reverse，加完，reverse

如果不想reverse，要先把兩邊長度的差距求出來，在遞迴時，短得先不要動，直到兩邊等長才一起動

# from 206
def reverseList(head: ListNode) -> ListNode:
        if head is None:
            return None
        elif head.next is None:
            return head
        else:
            now = head.next
            prev = head
            nextNow = head.next

            last = prev
            while now:
                nextNow = nextNow.next
                now.next = prev
                prev = now
                now = nextNow
            last.next = None
                
            return prev

# from 2
def addTwoNumbers2(l1: ListNode, l2: ListNode) -> ListNode:
    def size(l):
        ret = 0
        while l:
            l = l.next
            ret += 1
        return ret
    car = 0
    # premise: l1.len > l2.len
    if size(l2) > size(l1):
        l1, l2 = [l2, l1]
    ret = l1
    prev = l1
    while l1:
        tmp = l1.val + car + (l2.val if l2 else 0)
        l1.val = tmp % 10
        car = tmp // 10

        prev = l1
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    if car != 0:
        prev.next = ListNode(car)
    return ret    
    
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        return reverseList(addTwoNumbers2(reverseList(l1), reverseList(l2)))