This article is participating in the “Java Theme Month – Java Brush questions card”, activity link

Topic describes

Input parameters:

Represents two non-negative integers. .

  • Two non-empty linked lists

    • Number of nodes range :[1, 100]

    • 0 <= Node value <= 9

Title logic:

  • Returns a list representing the sum in the same form that asks you to add the elements of two lists at the corresponding positions

Output result:

  • Returns a linked list representing the sum of two numbers

Special note:

  • Rule: Each digit is stored in reverse order

  • Rule: And each node can store only one digit

  • Rule: Neither of these numbers begins with a 0, except for the number 0

The subject sample

Example 1

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

Example 2:

Input: L1 = [0], L2 = [0] Output: [0]Copy the code

Example 3:

Input: l1 =,9,9,9,9,9,9 [9], l2 =,9,9,9 [9] output:,9,9,9,0,0,0,1 [8]Copy the code

Thought analysis

We use variables to track the carry and simulate the bit-by-bit addition process starting with the table header containing the least significant bits.

Just as you would calculate the sum of two numbers on paper, there can be “spillovers” when we calculate the sum of two numbers.

  • For example, 5 + 7 = 12. In this case, we set the current bit value to 2 and carry carry = 1 into the next iteration.

  • Carry carry must be either 0 or 1, because the maximum sum that can occur when two numbers are added together (taking carry into account) is 9 + 9 + 1 = 19.

It is worth noting that the length of two lists may not be the same, so there may be a case where one list runs out of the other list, so the value of the list that runs out must be assigned to 0 until both lists run out of Null.

AC code

Implementation Method 1

class Solution { /* * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode p=new ListNode(-1); // create a new node ListNode res=p; int st=0; While (l1! =null || l2! L_1 int x= l1==null; l_1 int x= l1==null; 0:l1.val; int y= l2==null ? 0:l2.val; Int temp=(x+y+st); // Int value=temp%10; ListNode q=new ListNode(value); p.next=q; p=p.next; St =temp>=10? 1-0. // if the node is null and not forward l1= l1==null? l1:l1.next; l2= l2==null? l2:l2.next; } if(st==1){ ListNode q=new ListNode(st); p.next=q; } return res.next; }}Copy the code

Implementation Method 2 (Simplified version)

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(l1 ! =null|| l2 ! =null|| carry ! =0) {
            int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val)
            + carry;
            carry = s / 10;
            cur.next = new ListNode(s % 10);
            cur = cur.next;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        returndummy.next; }}Copy the code

Conclusion:

  1. The logical algorithm is relatively simple: the main idea is to rely on traversal linked list, so we must have a familiar concept of the structure of the linked list and traversal and maintenance mechanism.

  2. You have to think a little bit more about the relative carry and think about the carry forward. [0, 3]

  3. If the length of two linked lists is inconsistent, null processing is considered, and the processing mechanism is converted to 0.