Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what are the realization methods of the addition of two numbers". In the daily operation, I believe that many people have doubts about the implementation of the addition of two numbers. The editor consulted all kinds of materials and sorted out the simple and easy-to-use operation methods. I hope it will be helpful for you to answer the question of "what is the realization of the addition of two numbers?" Next, please follow the editor to study!

"the addition of two numbers"

Let's take a look at the description of the topic first.

I give you two non-empty linked lists that represent two non-negative integers. Each of them is stored in reverse order, and each node can only store one digit. Please add two numbers and return a linked list of sums in the same form. You can assume that neither of these numbers will start with 0 except for the number 0.

The addition of two numbers

The data structure of the linked list node is as follows:

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;}}

Title description

The description of the topic is relatively round. we can directly understand it as the addition of two multi-bit integers, but each bit of the integer is stored through a linked list. For example, the integer 342, stored through the linked list, should normally be 3-> 4-> 2, but when calculating, it often needs to be calculated from the low level, every ten into one, so the integer is directly expressed as 2-> 4-> 3 in the question. in this way, there is no need to reverse the order of the linked list, just add it.

The addition of two numbers

It should be noted that if the length of the two linked lists is different, it can be considered that there are several zeros behind the short linked list, and the traversal of the linked list ends, then if the carry value is greater than 0, a node with a value of 1 needs to be added to the result list.

Method 1: simulation

As mentioned above, the linked list is in reverse order, so you can add the corresponding numbers directly. The basic operation iterates through two lists, calculates their sum bit by bit, and adds them to the carry value of the current position.

For example, if the corresponding digits of two linked lists are N1 and N2, respectively, and the carry is carry (usually 0 and 1), then their sum is (N1 + N2 + carry), the number on the corresponding bit becomes (N1 + N2 + carry), and the new carry is (N1 + N2 + carry) / 10.

If the length of the two linked lists is not the same, the subsequent corresponding values of the short linked lists are all 0. If, after traversal, carray is greater than 0 (that is, equal to 1), a new node is added after the structure list

The implementation code is as follows:

Class Solution {public ListNode addTwoNumbers (ListNode L1, ListNode L2) {ListNode head = null, tail = null; int carry = 0; while (L1! = null | | L2! = null) {int N1 = L1! = null? L1.val: 0; int N2 = 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);} return head;}}

The calculation of the time complexity of the above method is related to the length of the linked list. For example, if the length of the two linked lists is m and n respectively, the number of times of traversal is max (m _ (less n)), that is, the maximum value is taken between m and n, so the time complexity is O (n).

Because each bit of the linked list needs to be calculated and stored, and one more bit is added if there is a carry at last, the longest linked list is max (mforce n) + 1, so the space complexity is O (n).

Through train of thought analysis, it is relatively easy to write the above code. But can this problem be solved in the form of recursion? Let's take a look at method two.

Method 2: recursion

The first method is very simple, just follow the normal logic of thinking. But there is a saying in the comment area, "No recursion, no soul." although most of the time, recursion is not necessarily more efficient. " So let's take a look at how to implement it in the form of recursion.

Class Solution {public ListNode addTwoNumbers (ListNode L1, ListNode L2) {return add (ListNode L1, ListNode L2, int carry) {if (l1==null & & l2==null & & carry = = 0) return null; int x = l1==null? 0: L1.Val; int y = l2==null? 0: L2.Val; int sum = x + y + carry; ListNode n = new ListNode (sum% 10) N.next = add (l1==null? Null: l1.next, l2==null? Null: l2.next, sum/10); return n;}}

The basic iterative logic loop of the above code is as follows:

The addition of two numbers

From the figure above, we can deduce the time complexity of recursive calls. The calculation of the time complexity of recursive calls essentially depends on: the number of recursions? The number of operations per recursion. So, how many times has the above method recursed? The number of recursions is also related to the length of the longest of the two linked lists, and it may end up with an extra round, so the number of recursions is n or nought 1, while the internal calculation does not change with n, and the number of execution is constant. Therefore, the overall time complexity is nasty 1 = O (n).

The space complexity is still related to the length of the resulting linked list, so it is still O (n).

At this point, the study of "what are the ways to realize the addition of two numbers" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.