This is the 11th day of my participation in the August More Text Challenge

Foreword daily touch fish topic, to weak (lazy) of their own to provide a practice (supervision) platform, a meal operation fierce as tiger, a look to submit beat 5%….

The title

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 a

Input: l1 = [2,4,3], l2 = [5,6,4] output: [7,0,8] explanation: 342 + 465 = 807.Copy 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

Ideas to build

  • A non-empty array in reverse order
  • The calculated results are still stored in reverse order
  • The first idea is to do the most violent way possible, walk through the list, get the node values, rearrange them, and insert a new list. Until I met death case:,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 [1], is a lesson.
  • Old old practical linked list method, while traversing the linked list, take out l1, L2 current node values, add, mod, divide by 10; Pay attention to carry (emphasis)
  • Rearrange linked lists

implementation

  1. Define an initialized list root with an initial value of 0
  2. Define the linked list to point to root with the carry value
  3. Loop through, and determine l1 and L2 are not empty
  4. L1 + L2 +carry= sumVal
  5. SumVal /10 carries the value, sumVal % 10 assigns the current node
  6. cursor.next = sumNode; cursor = sumNode; / / points to the cursor. The next
/** * Definition for singly-linked list. * 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; }} * * /
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode root = new ListNode(0);
            ListNode cursor = root;
            int carry = 0;
            while(l1 ! =null|| l2 ! =null|| carry ! =0) {intvalL1 = l1 ! =null ? l1.val:0;
                intvalL2 = l2 ! =null? l2.val:0;
                int sumVal = valL1 + valL2 +carry;
                carry = sumVal /10;

                ListNode sumNode = new ListNode(sumVal % 10);
                cursor.next = sumNode;
                cursor = sumNode;
                if(l1 ! =null)l1 = l1.next; 
                if(l2 ! =null)l2 = l2.next;

            }
            returnroot.next; }}Copy the code

The complexity of the

  • Time complexity: O(\ Max (m,n))O(Max (m,n)), where mm and nn are the lengths of two linked lists respectively. We’re going to traverse all the positions on both lists, and it only takes O(1)O(1) time to process each position.

  • Space complexity: O(1)O(1). Note that the returned value does not count space complexity.

conclusion

The idea of this problem is not difficult, but the last carry is easy to forget. 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.