Topic describes

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

Source: LeetCode link: leetcode-cn.com/problems/ad…

Their thinking

Reference: javascript unidirectional linked list implementation

Brief introduction to one-way linked lists:

  • Linked lists, like arrays, can be used to store a series of elements, but the implementation mechanism for linked lists and arrays is completely different.
  • Each element of a linked list consists of a node that stores the element itself and a reference (called a pointer or join in some languages) to the next element. Similar to a locomotive, one carriage carries passengers (data) and is connected to another carriage by nodes.

  • The head attribute points to the first node in the list; The last node in the linked list points to NULL;
  • When there are no nodes in the list, head points directly to NULL;

Definition of node class

/*** * Definition for singly-linked list. * Linked list node Definition; */ function ListNode(val){ this.val=val; this.next=null; }Copy the code

A:

  • The example is 342 + 465 = 807. Numbers are stored in reverse order
  • Function (l1, l2) param: l1 l2, are two linked lists connected by linked list nodes, list1, list2 as shown below;
    ListNode {
            val: 2,
            next: ListNode { val: 4, next: ListNode { val: 3, next: null } }
        } 
    ListNode {
        val: 5,
        next: ListNode { val: 6, next: ListNode { val: 4, next: null } }
    }
Copy the code
  • Define a list first node with val as head: new ListNode(“head”);
  • Define a pointer current to the head node; Sum is the sum of each bitwise sum. N is whether there is carry 1;
  • Through the while loop, new nodes are created and added bitwise, via the current link;
    • N1 +n2+n: each cycle adds up by bits and calculates carry n(0/1);
    • Sum %10(for example :(2+5)%10==7);
    • Current. Next Links a new node. And point current to the latest node. current=current.next;
    • ParseInt (sum/10); parseInt(sum/10);
    • If the current node L1 / L2 exists, it points to the next compute node: L1 /l2.next:
    • (ps: ListNode { val: 4, next: ListNode { val: 3, next: null })
  • Finally, the for loop is completed, and if there is a carry in the high order, a new ListNode(n) is created, and the link is passed through current. Next.
  • Finally, newNode:
   ListNode {
            val: 'head',
            next: ListNode { val: 7, next: ListNode { val: 0, next: ListNode{val:8,next:null} } }
        }
Copy the code
  • return newNode.next; Is the reverse result of the list addition

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
  // Add the two numbers to generate a new node;
  // 1. Define head as the head node of the new list
   let newNode=new ListNode('head')
   let current=newNode; 
  // define the decimal number n; Each calculation and sum;
  let n=0,sum=0;
  // 2, iterate through list l1,l2;
  while(l1||l2){
      letn1=l1? l1.val:0;
      letn2=l2? l2.val:0;
      sum=n1+n2+n;
      let nextNode=new ListNode(sum%10);
      current.next=nextNode;
      current=current.next;
      n=parseInt(sum/10);
      if(l1)l1=l1.next
      if(l2)l2=l2.next
  }// end of while
  // Check if there is a carry;
   if(n>0){
       current.next=new ListNode(n)
   }
   return newNode.next
};
Copy the code