Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

Given two integers represented by a linked list, each node contains one digit.

The digits are stored backwards, that is, at the head of the list.

Write a function to sum the two integers and return the result as a linked list.

Example:

Input: (7 -> 1 -> 6) + (5 -> 9 -> 2), namely 617 + 295 Output: 2 -> 1 -> 9, namely 912Copy the code

** Progression: ** Suppose these digits were stored forward, what would happen?

Example:

Input: (6 -> 1 -> 7) + (2 -> 9 -> 5), namely 617 + 295 Output: 9 -> 1 -> 2, namely 912Copy the code

Ii. Analysis of Ideas:

The ones bit is in the head of the list, so you only need to add the values of the nodes to the new list. Note the addition of the carry problem, which requires a temporary variable to store the carry.

The sum is computed when one of the nodes in linked lists 1 and 2 is not null. If one of the nodes is null and the other has a value, null is added as 0.

Step up, you can use two stacks, using the last in first out of the stack, first put two lists on the stack, and then take out the calculation. Note the order of the and nodes. The key is the operation a.ext = b.ext, b.ext = a, which reverses the node.

Iii. AC Code:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int temp = 0; / / carry
        ListNode sum = new ListNode(0); / / list and
        ListNode s = sum;
        while(l1 ! =null|| l2! =null) {int n = 0;
            if(l1 ! =null){
                n += l1.val;
                l1 = l1.next;
            }
            if(l2 ! =null){
                n += l2.val;
                l2 = l2.next;
            }
            n += temp;
            ListNode node = new ListNode(n%10);
            s.next = node;
            s = s.next;
            temp = n/10; / / carry
        }
        if(temp>0){
            s.next = new ListNode(temp);
        }
        returnsum.next; }}Copy the code

The advanced

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int temp = 0; / / carry
        ListNode sum = new ListNode(0); / / list and
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();

        while(l1! =null){
            s1.push(l1);
            l1 = l1.next;
        }
        while(l2! =null){
            s2.push(l2);
            l2 = l2.next;
        }

        while(! s1.isEmpty() || ! s2.isEmpty()){int n = 0;
            if(! s1.isEmpty()) n += s1.pop().val;if(! s2.isEmpty()) n += s2.pop().val; n += temp; ListNode node =new ListNode(n%10);
            temp = n/10;
            node.next = sum.next;
            sum.next = node;

        }
        returnsum.next; }}Copy the code

conclusion

This topic mainly exercises the new operation of the linked list, but also uses the last in first out feature of the stack, stick to the problem 15 days, come to learn with me to punch the clock.