Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

Topic 2: Add two numbers

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.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4] output: [7,0,8] explanation: 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:,9,9,9,0,0,0,1 [8]

Tip:

The number of nodes in each linked list is in the range [1, 100] 0 <= node. val <= 9

Ii. Analysis of Ideas:

  1. The problem looks like a simple addition of two numbers, but the problem introduces a linked list, which needs to be added using the related structure of a linked list.
  2. When two numbers with the same number of digits are added, perform simple carry. When two numbers with different numbers are added, add 0 in front of them manually. For example, add 191 and 80, which can be regarded as the sum of hi191 and 080
  3. Each bit must be computed with a carry value in mind, and at the end of the calculation must be computed with a carry value in mind.

Iii. AC Code:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode previousNode = new ListNode(0);
        ListNode currentNode = previousNode;
        int carryValue = 0;
        while(l1 ! =null|| l2 ! =null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carryValue;
            carryValue = sum / 10;
            sum = sum % 10;
            currentNode.next = new ListNode(sum);
            currentNode = currentNode.next;
            if(l1 ! =null)
                l1 = l1.next;
            if(l2 ! =null)
                l2 = l2.next;
        }
        if(carryValue == 1) {
            currentNode.next = new ListNode(carryValue);
        }
        returnpreviousNode.next; }}Copy the code

Iv. Summary:

For linked list structures, when the result is a header, it is usually necessary to initialize a pre-pointer, Pre, whose next node points to the real header, HEAD. The purpose of using pre-pointers is that there are no available node values when the list is initialized, and that the list construction process requires pointer movement, which in turn causes the head pointer to be lost and unable to return results.