0. Title link

Force buckle

 

1. Topic analysis

2. Add two numbers

Medium difficulty 7007

Here you are   Non empty   A linked list that represents two nonnegative integers. Each of these numbers is based on   Reverse order   And each node can only store   One   Number.

Please add the two numbers and return a linked list representing sum in the same form.

You can assume that neither of these numbers will be 0 except the number 0   start.

2. Variable setting and basic data type analysis

This problem is to give two linked lists with a length of at least 1 and the value in each node of the linked list   At least 0

Find the sum of two linked lists after adding  

That is, as the title

9 9 9 9 9 9 9

9 9 9 9

8 9 9 0 0 1 correspondence

Analysis is not difficult to find that in fact, this problem is in the primary school arithmetic problem

       9 9 9 9 9 9 9

+              9 9 9 9

----

1   0  0 0  9 9  9 8

That is, after the two numbers are read from right to left, add the results, and then fill in the new linked list from right to left

Here I think we should open up a new linked list, otherwise you don't know who is longer than the other two linked lists,

Adding, deleting and modifying the original data structure is too troublesome, and the situation is many and complex. It's better to open up a new linked list.

//The development of the new linked list here is very skilled, because it is well known that in Java, memory is divided into heap memory and stack memory

When new appears, an equal sign to the left of ne closely connects the stack and heap~

Among them, I learned that there are new sentences. I summarized:

Person person = new Person( );
int [] array  = new int [1024];
HashSet<Integer> set = new HashSet<> ();
String str = new String("Little red sun srs");

Here, when you construct a new linked list, you should give it a head node to point to it

  As for the head node, I asked Mr. Gao Bo, a former senior software development engineer of Alibaba, and got the above explanation.

In other words, if this problem declares a new linked list, open up memory on the heap to store the linked list.

         ListNode newHead=new ListNode(-10);
         ListNode temp=newHead;

This is extremely clever, and then the return value returns newHead.next, full of details.

3. Cycle condition, intermediate process, finishing work!

The cycle condition can be set to   Neither is empty  

         while(l1!=null&&l2!=null)
         {
            int sum=l1.val+l2.val;
            ListNode node = new ListNode(sum);
            temp.next=node;

             temp=temp.next;
             l1=l1.next;
             l2=l2.next;
         }

Then, new nodes are added continuously in the new linked list. The value of the new node is the sum of the values of the original two linked lists.

After the cycle, there must be three situations:

1. Single chain table 1 is finished, and 2 is not finished

2. Single chain table 2 is finished, and 1 is not finished

3. Two single linked lists go together

Don't worry about 3. In the case of 1 and 2,

1 after walking, connect the rest of the linked list 2 to the new linked list

2. After walking, treat the linked list 1 in the same way!

           if(l1==null)
         {
             temp.next=l2;
         }
         if(l2==null)
         {
             temp.next=l1;
         }
         ListNode cur=newHead;

After processing, the node values in each linked list are less than or equal to 18, and then they are cleared~

        //After merging the values of the two linked lists, start clearing the new linked list

         while(cur!=null)
         {
             if(cur.val>=10)
             {
                 if(cur.next==null)
                 {
                     cur.val-=10;
                     ListNode nb = new ListNode(1);
                     cur.next=nb;
                     break;
                 }
                 cur.val-=10;
                 cur.next.val++;
             }
             cur=cur.next;  
         }

It's better to open up a new linked list. Secondly, the difficulty of this problem is reduced. For example, if there is carry, the last carry must be 1, that is, the last one in the linked list. Consider the special situation~~

Finally, do not forget to return the value of the old fellow iron!

return newHead.next;

4. Summary

The total code is as follows:

/**
 * 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 newHead=new ListNode(-10);
         ListNode temp=newHead;
         while(l1!=null&&l2!=null)
         {
            int sum=l1.val+l2.val;
            ListNode node = new ListNode(sum);
            temp.next=node;

             temp=temp.next;
             l1=l1.next;
             l2=l2.next;
         }
                  if(l1==null)
         {
             temp.next=l2;
         }
         if(l2==null)
         {
             temp.next=l1;
         }
         ListNode cur=newHead;

         //After merging the values of the two linked lists, start clearing the new linked list

         while(cur!=null)
         {
             if(cur.val>=10)
             {
                 if(cur.next==null)
                 {
                     cur.val-=10;
                     ListNode nb = new ListNode(1);
                     cur.next=nb;
                     break;
                 }
                 cur.val-=10;
                 cur.next.val++;
             }
             cur=cur.next;  
         }

    return newHead.next;
    }
}

The old fellow who love it also supports us. We make progress together. We can't jump ten steps. Ten inferior horse riding is a great success.