两数相加

1、题目

image-20231009082429629

2、解法

迭代

两个链表存储方式相同，所以同一位置上的数字可以直接相加。设当前两个链表结点处相应位置的数字为\(n_1,n_2\),进位值为\(carry\),则和为\(n_1+n_2+carry\); 其中答案链表对应结点位置的数为\((n_1+n_2+carry)mod10\),新的进位值为\(⌊(n_1+n_2+carry)/10⌋\)。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0。此外，如果链表遍历结束后，有 \(carry>0\)，还需要在答案链表的后面附加一个节点，节点的值为\(carry\)。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode head = null, tail = null;

        int carry = 0;

        while(l1!= null||l2 != null){

            int num1 = (l1 != null)? l1.val:0;
            int num2 = (l2 != null)? l2.val:0;

            int sum = num1 + num2 +carry;

            if(head == null){
                head = tail = new ListNode(sum%10);
            }else{
                tail.next = new ListNode(sum%10);
                tail = tail.next;
            }
            carry = sum/10;

            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
        }

        if(carry>0){
            tail.next = new ListNode(carry);
        }

        return head;
    }
}

# 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]:
        cur = dummy = ListNode()
        flag = 0
        while l1 or l2 or flag:
            flag += (l1.val if l1 else 0)+(l2.val if l2 else 0)
            cur.next = ListNode(flag%10)
            flag //= 10
            cur =cur.next
            if l1: l1=l1.next
            if l2: l2=l2.next

        return dummy.next