leetcode-2 两数相加(AddTwoNumbers)-java

问题描述

给定两个链表分别代表两个非负整数，链表的每个结点分别存储整数的每位数字，且是逆序存储，即：数字最低位存储在链表表头，数字最高位存储在链表表尾。求解这两个整数的和并以相同的链表形式返回计算的结果。

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

问题分析

本题其实是一个大数相加问题，题目本身难度不大，需要考虑以下几个方面： 1. 设计好数据结构，反序存储数字，如数字932存储为2 -> 3 -> 9;

节点数据结构

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

1. 链表对应结点相加时增加前一个结点的进位，并保存下一个结点的进位；
2. 两个链表长度不一致时，要处理较长链表剩余的高位和进位计算的值；
3. 如果最高位计算时还产生进位，则还需要添加一个额外结点。

代码实现

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p = new ListNode(0);
    ListNode head = p;
    int carry = 0;
    while ( l1 != null || l2 != null || carry != 0) {
        int sum = ((l1 != null)? l1.val : 0) + ((l2 != null) ? l2.val : 0) + carry;
        carry = sum / 10;
        p.next = new ListNode(sum % 10);
        p = p.next;
        l1 = (l1 != null) ? l1.next : l1;
        l2 = (l2 != null) ? l2.next : l2;
    }
    return head.next;
}