Subject to introduce

Force buckle the second question: leetcode-cn.com/problems/ad…

Analysis of the

Since both input lists store digits in reverse order, numbers in the same position in the two lists can be added directly.

We iterate over both lists at the same time, calculating their sum bit by bit and adding it to the carry value of the current position. Specifically, if the numbers at the corresponding positions of the current two linked lists are N1 and n2, and the carry value is CARRY, their sum is N1 + n2 + CARRY; Where, the corresponding number in the answer list is (N1 + n2 + carry) mod 10, and the new carry value is (N1 + n2 + carry) / 10

If two lists are of different lengths, the short list can be considered to be followed by several zeros.

In addition, if the list has carry > 0 after traversal, you also need to append a node to the answer list with a value of CARRY.

The code is as follows:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Sentry node, the last node to store the head node of the new list
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        // Store carry
        int carry = 0;
        while(l1 ! =null|| l2 ! =null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            
            // Update the carry value
            carry = sum / 10;
            // Get the value of the current digits added without carrying
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            
            if(l1 ! =null) {
                l1 = l1.next;
            }
            
            if(l2 ! =null) { l2 = l2.next; }}// If the last carry has a value, it means that the number of digits is increased by 1, and a final node needs to be added
        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        returnpre.next; }}Copy the code

Complexity analysis

• Time complexity: O(Max (m,n)), where M and n are the lengths of two linked lists respectively. We’re going through all the positions on both lists, and it only takes O(1) time to process each position.

• Space complexity: O(1). Note that the returned value does not count space complexity.