题解 | #链表相加(二)#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null) return head2 ;
        if(head2 == null) return head1 ;
        //利用辅助栈来保存原链表的元素数值
        Stack<Integer> s1 = new Stack<>() ;
        Stack<Integer> s2 = new Stack<>() ;
        ListNode l1 = head1 ;
        ListNode l2 = head2 ;
        while(l1 != null) {
            s1.push(l1.val) ;
            l1 = l1.next ;
        }
        while(l2 != null) {
            s2.push(l2.val) ;
            l2 = l2.next ;
        }
        //开始相加
        ListNode pre = new ListNode(-1) ;
        ListNode cur = pre ;
        int jw = 0 ;//进位
        int bl = 0 ;//保留位
        while(!s1.isEmpty() && ! s2.isEmpty()) {
            bl = s1.pop() + s2.pop() + jw ;
            if(bl < 10) {
                jw = 0 ;
            } else {
                jw = 1 ;
                bl -= 10 ;
            }
            cur.next = new ListNode(bl) ;
            cur = cur.next ;
        }
        while(!s1.isEmpty()) {
            bl = s1.pop() + jw ;
            if(bl < 10) {
                jw = 0 ;
            } else {
                jw = 1 ;
                bl -= 10 ;
            }
            cur.next = new ListNode(bl) ;
            cur = cur.next ;
        }
        while(!s2.isEmpty()) {
            bl = s2.pop() + jw ;
            if(bl < 10) {
                jw = 0 ;
            } else {
                jw = 1 ;
                bl -= 10 ;
            }
            cur.next = new ListNode(bl) ;
            cur = cur.next ;
        }
        if(jw > 0) {
            cur.next = new ListNode(jw) ;
        }
        return reverseListNode(pre.next) ;
    }
    
    //翻转链表
    public ListNode reverseListNode(ListNode l) {
        if(l == null || l.next == null) return l ;
        ListNode pre = null ;
        ListNode cur = l ;
        ListNode nxt = null ;
        while(cur != null) {
            nxt = cur.next ;
            cur.next = pre ;
            pre = cur ;
            cur = nxt ;
        }
        return pre ;
    }
}