[record of question brushing] 2 Add two numbers

One 、 Title Description

source  

LeetCode

Here are two non empty linked lists , Represents two nonnegative integers . Each of them is stored in reverse order , And each node can only store one digit .

Please add up the two numbers , And returns a linked list representing sum in the same form .

You can assume that in addition to the numbers  0  outside , Neither of these numbers  0  start .

Example  1：

Input ：l1 = [2,4,3], l2 = [5,6,4]  Output ：[7,0,8]

explain ：342 + 465 = 807.

Example  2：

Input ：l1 = [0], l2 = [0]  Output ：[0]

Example  3：

Input ：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]  Output ：[8,9,9,9,0,0,0,1]

Tips ：

• The number of nodes in each list is in the range  [1, 100]  Inside

• 0 <= Node.val <= 9

• The title data guarantees that the number indicated in the list does not contain leading zeros

Two 、 Thought analysis ：

This topic can be seen as a mathematical operation process  

Vertical operation process of adding two numbers

Like in the picture above

• l1  Namely [3,4] l2  Namely [7,2]  The addition of corresponding positions in the linked list ,
  In the process of numerical operation , A process of adding from low to high .

• If there is a carry digit in addition , We need to record the number of digits , And add this carry number in one run   It's the one in the picture above
  1（tens）

• Then save the results of each time into a new linked list   For example, the result in the above figure is 70  Namely  [0,7]

3、 ... and 、 Code implementation

 public class ListNode {
 int val;
 ListNode next;
 ListNode() {}
 ListNode(int val) { this.val = val; }
 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

 //  Linked list of output results
 ListNode resultNode = new ListNode(0);
 ListNode head = resultNode;
 //  Record carry digit
 int carryNum = 0;

 while (l1 != null || l2 != null){
 //  Judge whether there is a value in the corresponding position in the two linked lists  （ Maybe even the digits of the linked list are inconsistent ）
 int num1 = l1 != null ? l1.val : 0;
 int num2 = l2 != null ? l2.val : 0;

 //  Add the numbers in the corresponding position   And add the carry digit
 int tmpnum = num1 + num2 + carryNum;

 //  Record the corresponding number to the linked list
 head.next = new ListNode(tmpnum % 10 );

 // Get carry
 carryNum = tmpnum / 10;

 head = head.next;

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

 }

 //  If there is a carry at the top   Fill a .
 if (carryNum > 0) head.next = new ListNode(carryNum);
 return resultNode.next;
 }
}


Running results

summary

We can turn the problem into a familiar model , Then we can better understand and come up with solutions .