题目描述

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例：

1 2	输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7

题解

翻转链表

之前做过个位数开始从左向右排列的链表相加的题目, 这道题考察了高位在左边

由于从个位开始按位数相加更加方便, 所以需要编写翻转链表的方法, 将输入的两个链表翻转, 然后再把结果翻转

public class lc445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode reverseL1 = reverseLinked(l1);
        ListNode reverseL2 = reverseLinked(l2);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int sum;
        int carry = 0;

        while (reverseL1 != null || reverseL2 != null) {
            sum = carry;

            if (reverseL1 != null) {
                sum += reverseL1.val;
                reverseL1 = reverseL1.next;
            }

            if (reverseL2 != null) {
                sum += reverseL2.val;
                reverseL2 = reverseL2.next;
            }

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

        }

        if (carry==1)
            cur.next = new ListNode(1);

        return reverseLinked(dummy.next);
    }


    public ListNode reverseLinked(ListNode head) {
        if (head == null)
            return null;
        ListNode cur = null;
        ListNode pre = head;

        while (pre != null) {
            ListNode t = pre.next;
            pre.next = cur;
            cur = pre;
            pre = t;
        }

        return cur;
    }
}