两数相加

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头

题目链接

分析

一定要看好题目，一开始我没看到逆序存储。结果兜了一大圈，才发现了错误，整个人都不好了。题目的算法很简单，就是模拟竖式计算，不过实现起来却真的很考验基本功，直接看标准答案吧：

标准答案

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);// 如果对象为null，next属性就没有了意义，所以一般要有一个初始的节点
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null) {// 一开始想到有序链表的合并了,想用“&&”解决问题，真不好用。还是“||”方便啊。
            int x = l1 == null ? 0 : l1.val;// 很妙啊
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if(l1 != null)
                l1 = l1.next; 
            if(l2 != null)
                l2 = l2.next;
        }
        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
}

灵感来源与有序链表合并的代码:对比一下，标准答案简洁了好多啊！

原创答案

class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null && l2 != null){
            int sum = l1.val + l2.val+carry;
            carry = sum / 10;
            sum %= 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1!=null){
            int sum = l1.val+carry;
            carry = sum / 10;
            sum %= 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            l1 = l1.next;
        }
        while (l2!=null){
            int sum = l2.val+carry;
            carry = sum / 10;
            sum %= 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            l2 = l2.next;
        }
        if(carry==1){
            cur.next=new ListNode(1);
        }
        return pre.next;
    }
}

补充

链表逆转

public ListNode reverse(ListNode l){
    ListNode pre = null; //前一个节点
    ListNode cur = l;
    ListNode next ; //后一个节点
    while(cur!=null){
        next = cur.next; //保存后一个节点地址
        cur.next = pre; // 逆转
        pre = cur;
        cur=next;
    }
    return pre;
}