Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

2. Add two numbers

In short, two linked lists containing several numbers are added together to get a new linked list. In other words, the sum of two addends and summations in an addition operation becomes a linked list of numbers.

Answer:

The first thing that comes to mind is to add the numbers of each node of the two lists. The result is the number of the corresponding node of the new list. This is actually the best case scenario, but there are a few things to consider.

  1. When two numbers add up to 10, you have to worry about rounding.
  2. If the final nodes add up to 10, the resulting linked list is longer than either argument list.
  3. The two lists are not necessarily the same length, so you need to add 0 when the nodes in the short list “don’t talk”.

First, write out the logical code you initially thought of:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode curr = pre;
        while(l1 ! =null|| l2 ! =null) {
            int x = l1.val;
            int y = l2.val;
            int sum = x + y;
            curr.next = new ListNode(sum);
            curr = curr.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        returnpre.next; }}Copy the code

Create pre first as the head node, so that you can directly follow the new node, eliminating the need to judge the first node in the loop, and finally return pre-.next. The curr is then created as a pointer to the current last node, and the newly created node is both the curr’s next node. Add the values of the corresponding positions of the two parameter lists each time as the value of the new node.

Then, we consider the case where adding two numbers requires rounding. Let’s say two numbers, 7 and 8, add up to 15. Then, the value of the corresponding position in the result list should be 5 (15%10), and the next node should be one more than the sum of its corresponding two numbers (15/10). So, outside the while loop, we create a carry variable that holds the tens digit of the sum.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode curr = pre;
        int carry = 0;
        while(l1 ! =null|| l2 ! =null) {
            int x = l1.val;
            int y = l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            curr.next = new ListNode(sum);
            curr = curr.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        returnpre.next; }}Copy the code

In this way, after calculating the sum of the two numbers, the ones digit is put into the corresponding node of the result list, and the tens digit is copied to the CARRY variable to be used for the number added after the sum of the two numbers in the next node. (Here carry can only be 0 and 1, and the sum of the two numbers is at most two digits).

Consider the second problem, the last node results in two digits, this problem is easy to solve, just after the execution of the loop, determine carry, if it is 1, then append a node with a value of 1 at the end.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode curr = pre;
        int carry = 0;
        while(l1 ! =null|| l2 ! =null) {
            int x = l1.val;
            int y = l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            curr.next = new ListNode(sum);
            curr = curr.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (carry == 1) {
            curr.next = new ListNode(carry);
        }
        returnpre.next; }}Copy the code

Finally, to solve the problem that two linked lists are not the same length, we need to modify two places. The first is at the beginning of the body of the loop. When taking the values x and y of the current nodes of the two lists, we need to determine whether the list has been traversed, that is, whether L1 or L2 is empty. If so, we cannot take their values, but assign x or Y a value of 0. The second is the end of the loop body, let the l1 and l2 point to the next node of the current node, make a judgment, because the two lists do not as long, short have no nodes in the list, but was still going on, then you need to determine the l1 and l2 is not null, then point to the next node, or complains.

Final code:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode curr = pre;
        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;
            curr.next = new ListNode(sum);
            curr = curr.next;
            if(l1 ! =null) {
                l1 = l1.next;
            }
            if(l2 ! =null) { l2 = l2.next; }}if (carry == 1) {
            curr.next = new ListNode(carry);
        }
        returnpre.next; }}Copy the code