Topic describes

You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.

You add the two numbers and return a linked list representing the sum in the same form.

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

The sample

Input: l1 = [2, 3], l2 =,6,4 [5] output:,0,8 [7] : 342 + 465 = 807.Copy the code

Subject interpretation

An integer is stored in a linked list. To put it simply, a positive decimal integer is split and stored in a linked list in reverse order. That is, the first node of the list corresponds to the ones place, the second node corresponds to the tens place, and the third node corresponds to the hundreds place… And so on.

Their thinking

Starting with the ones digit of the whole number is like going backwards from the first node in a list, and then summing each digit.

There are two problems to be noticed here. The first is the carry problem. If the sum of two numbers is greater than 10, we have to move forward one bit. The second problem is the unequal length of two lists, which requires traversing the list with the longest length.

Code reading

The function receives two arguments, which are actually the first nodes of the list. For a data structure like a linked list, if we get the first node, we get the whole list, so our return value is also the first node in the list.

A node is an object that has two attributes, val, which represents the value of the current node, and next, which records a node.

var addTwoNumbers = function (l1, l2) {
  // Head is the first node in the list and is used to return the result.
  // current is the current node of the linked list, used to store the results of each bit.
  let head = null, current = null;
  // carry is used to record the carry. The initial value is 0
  let carry = 0;
  // L1 and L2 both start at the first node in the list, and each loop fetchsthe next node until it is empty.
  L1 === null or L2 === null
  // only l1 and l2 are completed, so we use or
  while (l1 || l2) {
    // Fetch the value of the current node of both lists, and assign 0 if a node is empty
    const n1 = l1 ? l1.val : 0;
    const n2 = l2 ? l2.val : 0;
    // Sum the current bit with carry
    const sum = n1 + n2 + carry;
    // If head is empty, it is the first loop to assign the current computed node to head and current
    if(! head) { head = current =new ListNode(sum % 10);
    } else {
      // If it is not the first time through the loop, the node that evaluates the current result is assigned to the next node of the current
      current.next = new ListNode(sum % 10);
      // make current point to the next node
      current = current.next;
    }
    // Record the carry for the sum operation of the next loop
    carry = Math.floor(sum / 10);
    // At the end of each calculation, l1 and L2 must point to the next digit, because the two lists are not necessarily the same length
    if (l1) {
      l1 = l1.next;
    }
    if(l2) { l2 = l2.next; }}// At the end of the loop, if the carry value is greater than 0, the last node is created to hold the carry value
  if (carry > 0) {
    current.next = new ListNode(carry);
  }
  return head;
};
Copy the code