【Hot100】2. Add two numbers

Medium question
subject ：
Here are two for you Non empty The linked list of , Represents two nonnegative integers . Each of them is based on The reverse Stored in , And each node can only store a Numbers .
Please add up the two numbers , And returns a linked list representing sum in the same form .
You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

Answer key :
label ： Linked list
Think of two linked lists as traversal of the same length , If a linked list is short, fill in at the end 0, such as 987 + 23 = 987 + 230 =128
Traverse two linked lists at the same time , Calculate their sum bit by bit , And with the carry value of the current position $carry$ Add up .
Specific simulation process ：
We traverse two linked lists at the same time , Calculate their sum bit by bit , And add it to the carry value of the current position . To be specific , If the numbers in the corresponding positions of the current two linked lists are $x,y$, Carry value is $carry$, Then he is $x+y+carry$, The node value is $(x+y+carry)mod10$, The new carry value is $\frac{x+y+carry}{10}$.

If the two lists are all traversed , Carry value ==1, Then a node is appended to the new linked list , The node value is a carry value .

Tips ： For the list problem , When the return result is the header node , Usually you need to initialize a Pre pointer pre, The next node of the pointer points to the real header node head.
Using a pre pointer Purpose The reason is that there is no available node value when the linked list is initialized , And the construction process of linked list needs pointer movement , This will result in the loss of the head pointer , Unable to return a result .

Be careful ：
① Linked list must pass new ListNode( Node values ) Method to assign a value to a node
② To get the node value, use .val
③ Get the length corresponding to the two linked lists
④ Fill in zero at the end of the short linked list ( Because it's in reverse order )
⑤ Align and add considering carry , The current node value is after the remainder , The carry value is rounded to
⑥ The sum of two numbers is less than at most 20, therefore carry The maximum value of can only be 1

Code ：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        // Initialize carry value 
        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;

            carry = sum / 10;
            sum = sum % 10;

            // Add a node after the pre node and assign a value 
            cur.next = new ListNode(sum);

            // Move backward 
            cur = cur.next;

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

            // When the linked list traversal ends , If there is a carry value, add a carry value after the linked list 
            if(carry == 1){
    
                cur.next = new ListNode(carry);
            }
        }
        // Returns the entire list 
        return pre.next;

    }
}

class Solution {
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        // Define a new join table pseudo pointer , Pointer to the head , Return results 
        ListNode prev = new ListNode(0);
        // Define a carry pointer , Used to store when the sum of two numbers is greater than 10 When ,
        int carry = 0;
        // Define a movable pointer , Used to point to the location where the sum of two numbers is stored 
        ListNode cur = prev;
        // When l1  It's not equal to null or l2  Not equal to empty time , Go into the cycle 
        while(l1!=null || l2!=null){
    
            // If l1  It's not equal to null when , Take his value , be equal to null when , Just assign 0, Keep two linked lists with the same number of digits 
            int x= l1 !=null ? l1.val : 0;
             // If l1  It's not equal to null when , Take his value , be equal to null when , Just assign 0, Keep two linked lists with the same number of digits 
            int y = l2 !=null ? l2.val : 0;
            // The values of the two linked lists , Add additivity , And add the carry 
            int sum = x + y + carry;
            // Calculate the progression 
            carry = sum / 10;
            // Calculate the sum of two numbers , Exclude more than 10 Your request （ Greater than 10, Take the remainder ）
            sum = sum % 10;
            // Assign the summation number to the node of the new linked list ,
            // Note that at this time, you can't directly sum Assign a value to cur.next = sum. It will be reported at this time , Type mismatch .
            // So we need to create a new node at this time , Assign values to nodes 
            cur.next = new ListNode(sum);
            // Move the node of the new linked list back 
            cur = cur.next;
            // When linked list l1 It's not equal to null When , take l1  Move the node back 
            if(l1 !=null){
    
                l1 = l1.next;
            }
            // When linked list l2  It's not equal to null When , take l2 Move the node back 
            if(l2 !=null){
    
                l2 = l2.next;
            } 
        }
        // If the last two numbers , When there are carry digits when adding , Just carry the number , Give a new node to the linked list .
        // The sum of two numbers is less than at most 20, So the maximum value of can only be 1
        if(carry == 1){
    
            cur.next = new ListNode(carry);
        }
        // Return the head node of the linked list 
        return prev.next;
    }
}