LeetCode33
445.两数相加Ⅱ
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0] 输出：[0]
提示：
- 链表的长度范围为
[1, 100] 0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:p, q = l1, l2n1, n2 = 0, 0while p:p = p.nextn1 += 1while q:q = q.nextn2 += 1l3 = ListNode()p, q, j = l1, l2, l3while p and q:if n1 > n2:x = p.valy = 0n1 -= 1p = p.nextelif n2 > n1:x = 0y = q.valn2 -= 1q = q.nextelse:x = p.valy = q.valn1 -= 1n2 -= 1p = p.nextq = q.nextif x + y >= 10:node = ListNode(x+y-10)j.val += 1else:node = ListNode(x+y)j.next = nodej = j.nextpre = Nonecur = l3while cur:nxt = cur.nextcur.next = prepre = curcur = nxt#return prekk = prewhile kk:if kk.val >= 10:kk.val -= 10if kk.next:kk.next.val += 1else:node = ListNode(1)kk.next = nodekk = kk.nextpre1 = Nonecur1 = prewhile cur1:nxt1 = cur1.nextcur1.next = pre1pre1 = cur1cur1 = nxt1if pre1.val == 0:return pre1.nextelse:return pre1# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:pre1 = Nonecur = l1while cur:nxt = cur.nextcur.next = pre1pre1 = curcur = nxt#return pre1pre2 = Nonecur = l2while cur:nxt = cur.nextcur.next = pre2pre2 = curcur = nxt#return pre2cur = l3 = ListNode()carry = 0while pre1 or pre2 or carry:s = carry + (pre1.val if pre1 else 0) + (pre2.val if pre2 else 0)cur.next = ListNode(s % 10)carry = s // 10cur = cur.nextif pre1:pre1 = pre1.nextif pre2:pre2 = pre2.next#return l3.nextpre3 = Nonecur = l3.nextwhile cur:nxt = cur.nextcur.next = pre3pre3 = curcur = nxtreturn pre3不翻转链表：把单链表先依次储存到栈里，再依次出栈。