Bm11 list addition (II)

Ideas : First reverse the two linked lists, then add the values in turn and establish a new node to connect to the result linked list , Finally, reverse the linked list of results .

solution 1

public class Solution {
    
    /** * * @param head1 ListNode class  * @param head2 ListNode class  * @return ListNode class  */
    public ListNode addInList (ListNode head1, ListNode head2) {
    
        // write code here 
        if(head1 == null && head2 == null){
    
            return null;
        }
        if(head1 == null){
    
            return head2;
        }
        if(head2 == null){
    
            return head1;
        }
        // 1:  Reverse two linked lists 
        ListNode p1 = reverse(head1);
        ListNode p2 = reverse(head2);
        int approve = 0;
        int val = 0;
        ListNode ret = new ListNode(1);
        ListNode cur = ret;
        // 2:  If the corresponding two nodes are not empty, add and record the carry , Finally, create nodes with the results and string them in the result linked list 
        while(p1 != null && p2 != null){
    
            val = (p1.val + p2.val + approve) % 10;
            approve = (p1.val + p2.val + approve) / 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            p1 = p1.next;
            p2 = p2.next;
        }
        while(p1 != null){
    
            val = (p1.val + approve) % 10;
            approve = (p1.val + approve) / 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            p1 = p1.next;
        }
        while(p2 != null){
    
            val = (p2.val + approve) % 10;
            approve = (p2.val + approve) / 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            p2 = p2.next;
        }
        // 3:  Add a value of 1 The node of 
        if(approve == 1){
    
            cur.next = new ListNode(1);
        }
        // 4:  Reverse the final result of construction again 
        return reverse(ret.next);
    }
    public ListNode reverse(ListNode head){
    
        ListNode cur = head;
        ListNode prev = null;
        while(cur != null){
    
            ListNode nextNode = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextNode;
        }
        return prev;
    }
}

solution 2

public class Solution {
    
    /** * * @param head1 ListNode class  * @param head2 ListNode class  * @return ListNode class  */
    public ListNode addInList (ListNode head1, ListNode head2) {
    
        // write code here
        // 1:  Create two stacks and put the two linked lists into the stack respectively 
        Stack<Integer> stack1=new Stack();
        Stack<Integer> stack2=new Stack();
        int cnt=0;
        int sum=0;
        ListNode dummy=new ListNode(0);
        while(head1!=null){
    
            stack1.add(head1.val);
            head1=head1.next;
        }
        while(head2!=null){
    
            stack2.add(head2.val);
            head2=head2.next;
        }
        // 2:  Take out the elements of the two stacks at the same time and add them , Finally, connect to the result linked list 
        while(!stack1.isEmpty()||!stack2.isEmpty()||cnt>0){
    
            int c=!stack1.isEmpty()?stack1.pop():0;
            int d=!stack2.isEmpty()?stack2.pop():0;
            sum=(c+d+cnt)%10;
            cnt=(c+d+cnt)/10;
            ListNode node=new ListNode(sum);
            //  Here we use the method of head insertion to connect, which saves the process of final reversal 
            node.next=dummy.next;
            dummy.next=node;
        }
        return dummy.next;
    }
}