For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: Add two numbers

Title source: leetcode-cn.com/problems/ad…

Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit.

If we add these two numbers together, a new linked list is returned to represent their sum.

You can assume that neither of these numbers will start with 0, except for the number 0.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Cause: 342 + 465 = 807Copy the code

The problem solving scheme

Just to be clear, the difficulty of this problem was medium, so I went back and worked on it from the beginning down, and the number of the problem was actually 200+ yesterday, and I found that most of the rest of the problem turned into SQL and bash scripts, so I decided to go back to the beginning and work on it down.

This problem looks down to feel not like the medium difficulty of the problem, the feeling is not as difficult as the binary number of the previous two days, the binary number of the problem looked at the basic belong to a face meng forced do not know what to do, this problem after reading the basic idea is some.

Just iterate over the two lists and add them up bitwise. If there are any carries, note them down and add them to them in the next iteration.

Because this problem gives the direct is the reverse order of the number, so the direct order of the front and back iteration is good, there is no slippery.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode pre = new ListNode(0);
    ListNode curr = pre;
    // Define the carry
    int carry = 0;
    while(l1 ! =null|| l2 ! =null) {
        intx = (l1 ! =null)? l1.val :0;
        inty = (l2 ! =null)? l2.val :0;
        int sum = x + y + carry;
        // carry flag
        carry = sum / 10;
        // Construct the next node
        curr.next = new ListNode(sum % 10);
        // Point to the next node
        curr = curr.next;
        if(l1 ! =null) l1 = l1.next;
        if(l2 ! =null) l2 = l2.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return pre.next;
}
Copy the code

The only thing to notice in this scheme is that we define a header pre, and why we define pre, because when we do the next iteration, we need to move the pointer, and if we don’t have the pre, we can’t move the pointer during the next iteration.

And THEN I looked at the answer, and I found that this was the only solution, and the rest were variations of this solution, either defining two other data structures, like queues, iterating through the queue, putting the data in the queue, and then iterating through the queue.

There is also the problem of iterating the linked list first, making the two integers into int directly, then adding them up, and finally iterating the number into the linked list. However, in this scheme, we need to consider the problem of type overflow, perhaps making the type of double or long, and also pay attention to the accuracy problem during calculation.