链表两数相加

逆序

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

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

你可以假设除了数字 0 之外，这两个数都不会以 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: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        p = dummy
        carry = 0
        while l1 or l2 or carry:
            l1_val = l1.val if l1 else 0
            l2_val = l2.val if l2 else 0
            tmp = l1_val + l2_val + carry
            l_tmp = ListNode(tmp%10)
            carry = tmp//10
            p.next = l_tmp
            p = l_tmp
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next
        

        

顺序

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 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: ListNode, l2: ListNode) -> ListNode:
        l1_stack = []
        l2_stack = []
        while l1:
            l1_stack.append(l1.val)
            l1 = l1.next
        
        while l2:
            l2_stack.append(l2.val)
            l2 = l2.next
        
        carry = 0
        dummy = ListNode()
        while l1_stack or l2_stack or carry:
            l1_val = l1_stack.pop() if l1_stack else 0
            l2_val = l2_stack.pop() if l2_stack else 0
            tmp = l1_val + l2_val + carry
            tmp_Node = ListNode(tmp%10)
            carry = tmp//10
            tmp_Node.next = dummy.next
            dummy.next = tmp_Node
        
        return dummy.next