Leetcode daily practice (sum of two numbers)

The title is as follows ：

Here are two non empty linked lists , Represents two nonnegative integers . Each of them is based on The reverse Stored in , And each node can only store a Numbers . Please add up the two numbers , And returns a linked list representing sum in the same form .
You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

The subject is well understood , I'll give you two linked lists , such as 243 and 564, You need to get the values represented by the linked list in reverse order , Namely 342 and 465, Add these two numbers together , Get the results 807, Save a linked list in reverse order and return .

After understanding the meaning of the title , Let's analyze first , The idea of this problem is relatively simple , First, traverse two linked lists , And reverse the traversal results , Get two numbers , And then add it up to get the result , And then put it into the linked list in reverse order .

First, we need to get the values represented by the two linked lists ：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        //  Traverse l1 The linked list gets the value 
        StringBuilder sb = new StringBuilder();
        while (l1 != null) {
    
            sb.append(l1.val);
            l1 = l1.next;
        }
        //  Reverse the numerical order 
        String str1 = sb.reverse().toString();
        Integer num1 = Integer.valueOf(str1);

        //  Empty sb
        sb.setLength(0);

        //  Get the linked list in the same way l2 The numerical 
        while (l2 != null) {
    
            sb.append(l2.val);
            l2 = l2.next;
        }
        String str2 = sb.reverse().toString();
        Integer num2 = Integer.valueOf(str2);

        //  Addition of two numbers 
        int result = num1 + num2;

        System.out.println(num1 + "+" + num2 + "=" + result);
        return null;
    }

Running results ：

342+465=807

After getting the result , Just create a new linked list , Put the results in a new list in reverse order ：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        //  Traverse l1 The linked list gets the value 
        StringBuilder sb = new StringBuilder();
        while (l1 != null) {
    
            sb.append(l1.val);
            l1 = l1.next;
        }
        //  Reverse the numerical order 
        String str1 = sb.reverse().toString();
        Integer num1 = Integer.valueOf(str1);

        //  Empty sb
        sb.setLength(0);

        //  Get the linked list in the same way l2 The numerical 
        while (l2 != null) {
    
            sb.append(l2.val);
            l2 = l2.next;
        }
        String str2 = sb.reverse().toString();
        Integer num2 = Integer.valueOf(str2);

        //  Addition of two numbers 
        int result = num1 + num2;
        //  Organize the results into a linked list 
        String strResult = String.valueOf(result);
        char[] chars = strResult.toCharArray();
        ListNode listNode = new ListNode();
        ListNode temp = listNode;
        for (int i = chars.length - 1; i >= 0; --i) {
    
            if (i == 0) {
    
                temp.val = Integer.parseInt(String.valueOf(chars[i]));
                //  For the tail node , Its pointer field is empty 
                temp.next = null;
            } else {
    
                temp.val = Integer.parseInt(String.valueOf(chars[i]));
                temp.next = new ListNode();
                temp = temp.next;
            }
        }
        return listNode;
    }

Are some very simple list operation , If you can't link lists yet , Data structure needs to make up lessons , Traverse the returned list to get the result ：

708

Put the code in with joy LeetCode Up operation , It didn't pass ：

It turns out that the test data is too big , Lead to int Type can't hold , Then change it to long type ：

......
Long num1 = Long.valueOf(str1);
Long num2 = Long.valueOf(str2);
Long result = num1 + num2;
......

It still didn't pass ：

My day, , The test data is so long , There's no way out. , We changed it to BigDecimal That's all right. , The final code ：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        //  Traverse l1 The linked list gets the value 
        StringBuilder sb = new StringBuilder();
        while (l1 != null) {
    
            sb.append(l1.val);
            l1 = l1.next;
        }
        //  Reverse the numerical order 
        String str1 = sb.reverse().toString();
        BigDecimal decimal1 = new BigDecimal(str1);

        //  Empty sb
        sb.setLength(0);

        //  Get the linked list in the same way l2 The numerical 
        while (l2 != null) {
    
            sb.append(l2.val);
            l2 = l2.next;
        }
        String str2 = sb.reverse().toString();
        BigDecimal decimal2 = new BigDecimal(str2);


        //  Addition of two numbers 
        BigDecimal resultDecimal = decimal1.add(decimal2);
        //  Organize the results into a linked list 
        String strResult = resultDecimal.toString();
        char[] chars = strResult.toCharArray();
        ListNode listNode = new ListNode();
        ListNode temp = listNode;
        for (int i = chars.length - 1; i >= 0; --i) {
    
            if (i == 0) {
    
                temp.val = Integer.parseInt(String.valueOf(chars[i]));
                temp.next = null;
            } else {
    
                temp.val = Integer.parseInt(String.valueOf(chars[i]));
                temp.next = new ListNode();
                temp = temp.next;
            }
        }
        return listNode;
    }

The test passed ：

We can see that the execution time is relatively long , Only defeated 18.79% Users of , Let's analyze the reasons for the long execution time , The first is the traversal of the linked list , We traversed the linked list twice , And then the creation of the linked list , These are very time-consuming operations , Is there any way to complete the requirements of the topic with only one traversal ？

The title indicates that the numbers in the linked list are stored in reverse order , This just gives us a convenient way to deal with it , We can traverse two linked lists at the same time , And take out two values in the same position of two linked lists , Add it up and put it directly into the newly created linked list , such as 243 and 564 Linked list ：

Because values are stored in reverse order , So the first element of a linked list is actually the last number of values , take 2 and 5 Add up to get 7, So the last digit of the result is 7, And put it in a new linked list , As the first node ：

then l1 and l2 Move back one position ：

The sum of the two numbers at this position is 10, Here we need to consider the carry problem , Let the value of the current position be 0, And move forward 1, Just divide the sum by 10, You can get carry ; such as 10 Divide 10 be equal to 1, Just move on 1,23 Divide 10 be equal to 2, Just move on 2. And let the result of the addition be modulo 10 You can get the number of results for the current position , such as 10 model 10 be equal to 0, The current position is 0,23 model 10 be equal to 3, The current position is 3. Thus we can see that , The penultimate number of the result is 0, Put it in a new linked list ：

l1、l2 Continue backward ：

The sum of the two numbers in this position equals 7, It needs to be noted that carry has to be added , So the number one result is 8, Put it in a new linked list ：

here l1、l2 Move backward , The result is empty. , So the calculation is over , In this way, we get the result list directly through a traversal .

Of course , We also need to consider the case that two linked lists are not the same length , such as ：

In this case , The first two numbers are the same ,5 Add 2 be equal to 7, Put it in a new linked list ,6 Add 4 be equal to 10, Move forward 1, take 0 Put it in a new linked list , here l1、l2 Move back again ,l1 It's empty , but l2 It's still worth it , At this time we give l1 One occupancy , Let it is equal to the 0, So you can continue to add , here 4 Add 0, Plus carry equals 5, So the end result is ：

So you get the code ：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        //  The head pointer of the new list 、 Tail pointers are initialized to null
        ListNode head = null, tail = null;
        //  The initialization carry is 0
        int carry = 0;
        //  At the same time through l1 and l2 Linked list 
        while (l1 != null || l2 != null) {
    
            //  Deal with the case that two linked lists are not equal in length , If a list traversal ends , Node is null, Let it be equal to 0
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            //  Addition of two numbers , Remember to add carry 
            int sum = n1 + n2 + carry;
            //  Using tail insertion method to build a new linked list 
            if (head == null) {
    
                head = tail = new ListNode(sum % 10); //  model 10 Get the value of the current position 
            } else {
    
                tail.next = new ListNode(sum % 10); //  model 10 Get the value of the current position 
                tail = tail.next;
            }

            //  Calculated carry 
            carry = sum / 10;
            if (l1 != null) {
    
                l1 = l1.next;
            }
            if (l2 != null) {
    
                l2 = l2.next;
            }
        }
        //  If two linked list traversal after the end , There is still carry , Then carry should become a new one 
        if (carry > 0) {
    
            tail.next = new ListNode(carry);
        }
        return head;
    }

Because the calculated results need to be put into the new linked list in order , So here we use the tail insertion method to build a new linked list .

Finally, submit the code to LeetCode On , The test passed ：