Leetcode面试经典150题-2.两数相加

解法都在代码里，不懂就留言或者私信

理论上提交这个就是最优解

字节考过不下20次，这个高居字节面试榜第9名

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**本题从头到尾相加，还算比较简单，就每一位相加，算出进位值然后给下一位
    每一位都这么加，直到某个位不再有数停止遍历，如果有某个还不为空，就继续遍历这一个链表
    最后如果有进位，单独出一位（如果有就是1，这是常识） */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        /**和一个空的数相加相当于加了0，返回自己即可 */
        if(l1 == null || l2 == null) {
            return l1 == null? l2 : l1;
        }
        /**carry表示进位,整个计算过程中我们就用这一个进位变量*/
        int carry = 0;
        /**head是整个结果链表的头节点 */
        ListNode head = null;
        ListNode lastConnect = null;
        while(l1 != null && l2 != null) {
            /**毛和（进位之前的） */
            int grossSum = l1.val + l2.val + carry;
            /**当前位进位之后的值*/
            int curNum = grossSum % 10;
            /**进位 */
            carry = grossSum / 10;
            ListNode cur = new ListNode(curNum);
            /**如果这是结果的第一个节点，把它设置为头和最后一个被连上的节点 */
            if(head == null) {
                head = cur;
                lastConnect = cur;
            } else {
                lastConnect.next = cur;
                lastConnect = cur;
            }
            /**当前处理完毕，都跳下一个 */
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null) {
            /**如果链表1还没有用完，那就继续计算它和进位 */
            int grossSum = l1.val + carry;
            int curNum = grossSum % 10;
            carry = grossSum / 10;
            ListNode cur = new ListNode(curNum);
            /**这个时候不会出现结果链表还没初始化的情况，不用判断head是不是为null*/
            lastConnect.next = cur;
            lastConnect = cur;
            l1 = l1.next;
        }
        while(l2 != null) {
            /**如果链表1还没有用完，那就继续计算它和进位 */
            int grossSum = l2.val + carry;
            int curNum = grossSum % 10;
            carry = grossSum / 10;
            ListNode cur = new ListNode(curNum);
            /**这个时候不会出现结果链表还没初始化的情况，不用判断head是不是为null*/
            lastConnect.next = cur;
            lastConnect = cur;
            l2 = l2.next;
        }
        /**如果最后还有进位，那就进位作为最后一个节点 */
        if(carry != 0) {
            ListNode carryNode = new ListNode(carry);
            lastConnect.next = carryNode;
        }
        return head;
    }
}