LeetCode-2: Add two numbers

Welcome to my personal website to visit this article

LeetCode:https://leetcode-cn.com/problems/add-two-numbers/

LeetCodeCn:https://leetcode-cn.com/problems/add-two-numbers/

The title suggests

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

Input :(8 -> 4 -> 9) + (5 -> 6 -> 3)

Output: 3 -> 1 -> 3 -> 1

The problem solving method

Elementary mathematics

The math is simple, but you need to deal with a few special cases, when the length of the two lists is different, the next bit of the short list is filled with 0

In the process of adding two links, add a variable to record the carry situation of low and like high. After traversing the two linked lists, check this value and decide whether to add high.

Diagram related ideas

The two linked lists entered here are 8->4->9 and 5->6->3

Sum =13; sum%10; carry = sum/10 =1; sum%10 =1;

Repeat the previous step, insert 1 into the end of the result list, and calculate CARRY = 1

Repeat the previous step, insert 3 into the end of the result list, and calculate CARRY = 1

When both L1 and L2 are traversed, the contents of carry are checked and it is found that carry is not 0, then a carry is inserted as the high-level content

Code implementation

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode temp = result;
    int carry = 0;

    while(l1 ! =null|| l2 ! =null) {
        inta = (l1 ! =null)? l1.val :0;
        intb = (l2 ! =null)? l2.val :0;
        int sum = carry + a + b;

        carry = sum / 10;
        temp.next = new ListNode(sum % 10);
        temp = temp.next;

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


    if (carry > 0) {
        temp.next = new ListNode(carry);
    }
    return result.next;
}
Copy the code

You are welcome to pay attention to the relevant code and put forward suggestions for improvement