2.两数相加

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

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

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

Example:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

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 non-negative integer.

解题思路:

  • Create a new linked list to store the sum.
  • Initialize a carry variable to 0.
  • Iterate through the input lists, adding the corresponding digits and carrying over any overflow.
  • For each iteration:
    • Add the current digits of the two lists, along with the carry.
    • Calculate the new carry and the digit to add to the sum list.
    • Add the new digit to the sum list.
  • If there is a remaining carry, add it to the sum list.
  • Return the sum list.

Code:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
     dummy := &ListNode{Val: 0, Next: nil}
     curr := dummy
     carry := 0

    for l1 != nil || l2 != nil || carry != 0 {
         sum := carry
         if l1 != nil {
             sum += l1.Val
             l1 = l1.Next
         }
         if l2 != nil {
             sum += l2.Val
             l2 = l2.Next
         }
         carry = sum / 10
         curr.Next = &ListNode{Val: sum % 10}
         curr = curr.Next
    }

     return dummy.Next
}