LeetCode.面试题02.05-链表求和-题解分析

题目来源

面试题 02.05. 链表求和

题目详情

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入： (7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出： 2 -> 1 -> 9，即912

进阶： 思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入： (6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出： 9 -> 1 -> 2，即912

题解分析

题目的要求是对链表的节点进行求和。题目的难点在于两个链表的长度可能不同，而且每个节点只能存放一个数位的元素。

这里最直接的解法就是模拟法，或者叫做遍历法，同时遍历这两个链表并进行加法运算，构造出一个新的结果链表。考虑到这里是一个反向链表，可以直接从头开始遍历，因此，这个题目也可以看成是一个子问题的题目即使用递归的思想解决。

使用递归的方法相对容易理解，而且写法比较简单。在每一轮递归的过程中，需要同时记录进位，在两个链表都遍历结束的时候，因为每个节点只能存放一个位的元素，因此可能会存在进位元素，需要放在一个新的尾部节点中。

java实现

/**
 * 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) {
        return dfs(l1, l2, 0);
    }

    private ListNode dfs(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        int sum = carry;
        if (l1 == null && l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        } else if (l2 == null && l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        } else if ((l1 != null) && (l2 != null)) {
            sum += (l1.val + l2.val);
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode node = new ListNode(sum % 10);
        node.next = dfs(l1, l2, sum / 10);
        return node;
    }
}