Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card for the second day 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example of original problem

  • 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], 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
  • The question data ensures that the numbers represented in the list do not contain leading zeros

🌞

🌻 c # method

The idea is to do a while loop through two lists, add up the values of each of them, and if there is a carry, store the carry in the Other variable for the next loop. The Ohter is reset again on the next loop.

code

    public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
            // Define the return value
            var result = new ListNode(- 1);
            // Define the object for the loop, specifying the parameter to temp
            var temp = result;
            // The ten digits of the sum of the previous round
            int Other = 0;
            do
            {
                // Fetch the values of numbe1 and number2
                var number1 = l1 == null ? 0 : l1.val;
                var number2 = l2 == null ? 0 : l2.val;
                // Calculates the sum of the two numbers and adds the value of the previous round
                var sum = number1 + number2 + Other;
                // Compute the bits
                var value = sum % 10 ;
                // Computes the tens place and assigns the value
                Other = sum / 10;
                // Add data to the circular list
                temp.next = new ListNode(value);
                // The temp object used for the loop is assigned to the next object in the loop list
                temp = temp.next;
                //l1 l2 points to its next value in the listl1 = l1? .next; l2 = l2? .next; }while(l1 ! =null|| l2 ! =null|| Other! =0);
            return result.next;
        }


Copy the code

The execution result

The execution time is 116ms, and the memory consumption is 27.7 MB.

🎋Java method: emulation

Ideas and Algorithms

Since both input lists store digits in reverse order, numbers in the same position in the two lists can be added directly.

We iterate over both lists at the same time, calculating their sum bit by bit and adding it to the carry value of the current position. Specifically, if the numbers in the corresponding positions of the current two linked lists are N1,n2n1,n2, and the carry value is \textit{carry}carry, the sum of them is N1 +n2+\ Textit {carry}n1+n2+carry;

(n1+n2+\textit{carry}) \bmod 10(n1+n2+carry)mod10 The new carry value is \lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor⌊ 10n1+n2+carry ⌋.

If two lists are of different lengths, you can assume that the short list is followed by several 00’s.

In addition, if there is \textit{carry} > 0CARRY >0 at the end of the list, you also need to append a node to the end of the answer list with the value \ Textit {carry}carry.

code

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while(l1 ! =null|| l2 ! =null) {
            intn1 = l1 ! =null ? l1.val : 0;
            intn2 = l2 ! =null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if(l1 ! =null) {
                l1 = l1.next;
            }
            if(l2 ! =null) { l2 = l2.next; }}if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        returnhead; }}Copy the code

The execution result

The execution time is 2ms, and the memory consumption is 38.8 MB.

Complexity analysis

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.

💬 summary

  • Today is the second day of buckle algorithm card, just started some strange, behind will be more and more skilled!
  • This paper uses C# and Java programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!