List summation [dummy+ tail interpolation + function processing list reference common pit]

Preface

There are two ways to deal with linked lists , First of all , Is to directly operate the linked list , For simple cases ; second , use dummy As the head node of the new linked list , Insert the qualified nodes of the old linked list with the header / The tail interpolation method is connected to dummy/dummy-tail Back .
besides , When the function is passed in the sum of linked list node references , The reference variables of the current function and the calling function are the variables on the two stack frames , Not the same .

One 、 Sum of linked list

Two 、dummy+ The tail interpolation

package everyday.medium;

//  Sum of linked list 
public class AddTwoNumbers {
    
    /* target： utilize dummy, Insert the generated node in the way of tail interpolation .  The core of list summation ： If you write a function to handle the remaining long linked list , The tail interpolation method will appear tail When the pointer does not move , because Java Only pass value , Two tail There are already two stack variables . */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        //  With dummy As a new linked list 
        ListNode dummy = new ListNode(0);
        //  The tail interpolation 
        ListNode tail = dummy;
        //  carry 
        int plus = 0;
        //  Sum and carry 
        while (l1 != null && l2 != null) {
    
            int sum = l1.val + l2.val + plus;
            int val = sum % 10;
            ListNode n = new ListNode(val);

            tail.next = n;
            tail = n;
            // for cycle
            l1 = l1.next;
            l2 = l2.next;
            plus = sum / 10;
        }
        //  Handle long linked lists that are not empty .
        processLongList(tail, l1 == null ? l2 : l1, plus);
        return dummy.next;
    }

    //
    private void processLongList(ListNode tail, ListNode l, int plus) {
    

        while (l != null) {
    
            int sum = l.val + plus;

            int val = sum % 10;
            ListNode n = new ListNode(val);

            tail.next = n;
            tail = n;

            l = l.next;
            plus = sum / 10;
        }
        //  By the way, the plus  Not for 0 The situation is handled , Otherwise, you need to tail/plus All back to , notes ： there tail It's value passing , And the function above tail It's already two variables .
        if (plus != 0) tail.next = new ListNode(plus);
    }

    // Definition for singly-linked list.
    public class ListNode {
    
        int val;
        ListNode next;

        ListNode(int x) {
    
            val = x;
        }
    }
}

summary

1）dummy+ Tail interpolation operation linked list , Unified operation .
2） Pass a reference to the function , Then the reference of the two functions is different , A new reference variable memory is allocated on the stack frame of the new function , Used to point to the heap address .

reference

[1] LeetCode Sum of linked list