题解 | #连续子数组的最大和#

import java.util.Stack;

/*
 * 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) {
        // write code here
        if (null == head1 && null == head2) {
            return null;
        }
        if (null == head1) {
            return head2;
        }
        if (null == head2) {
            return head1;
        }
        // 具体代码实现
        // 将两个链表进行反转
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        // 定义两个指针，初始时分别指向两个链表的头节点
        ListNode ln1 = head1;
        ListNode ln2 = head2;
        // 定义一个整型变量，用于存放进位
        int an = 0;
        // 定义一个整型变量，用于存放余数
        int val = 0;
        // 定义一个用于临时存储数据的整型变量
        int ts = 0;
        // 定义一个栈，用于存放最终的结果
        Stack<ListNode> result = new Stack<>();
        
        while (null != ln1 && null != ln2) {
            ts = ln1.val + ln2.val + an;
            val = ts % 10; // 余数
            an = ts / 10; // 进位
            // 这里不要贪心，还是老老实实新建一个节点吧
            result.push(new ListNode(val));
            // 指针后移一位
            ln1 = ln1.next;
            ln2 = ln2.next;
        }
        // 定义另一个指针
        ListNode ln = null != ln1 ? ln1 : (null != ln2 ? ln2 : null);
        if (null == ln) {
            // 如果都为空
            if (0 != an) {
                result.push(new ListNode(1));
            }
        }
        else {
            // 如果有一个不为空，将剩下的节点压栈
            while (null != ln) {
                ts = ln.val + an;
                val = ts % 10; // 余数
                an = ts / 10; // 进位
                result.push(new ListNode(val));
                ln = ln.next;
            }
            if (0 != an) {
                result.push(new ListNode(1));
            }
        }
        // 最终，将栈里面的节点依次弹出，就是我们想要的最终结果
        head1 = result.pop();
        ln1 = head1;
        while (!result.isEmpty()) {
            ln1.next = result.pop();
            ln1 = ln1.next;
        }
        return head1;
    }
    
    // 反转链表
    public static ListNode reverseList(ListNode head) {
        if (null == head) {
            return null;
        }
        if (null == head.next) {
            return head;
        }
        // 定义一个辅助栈
        Stack<ListNode> stack = new Stack<>();
        // 定义一个指针
        ListNode ln = head;
        // 具体代码实现
        while (null != ln) {
            stack.push(ln);
            ln = ln.next;
        }
        head = stack.pop();
        ln = head;
        while (!stack.isEmpty()) {
            ln.next = stack.pop();
            ln = ln.next;
        }
        // 别忘了，末尾置为null
        ln.next = null;
        // 返回头节点
        return head;
    }
}