Java算法题-解析 "两数相加" 算法问题

题目：

给定两个非空链表，代表两个非负整数。链表中每个节点包含一个数字，且这些数字以逆序的方式存储，即个位位于链表开头。请将这两个数相加，并返回以链表形式表示的结果。

引言：

"两数相加" 是一道典型的链表操作题，要求实现链表的遍历和数学运算。实际编程中，这类题目经常出现，特别是在处理大整数相加和进位问题时。通过解决这道问题，我们可以更好地理解链表操作的要点，同时也能够应对类似的数学运算挑战。

算法思路：

这个问题可以通过模拟两数相加的过程来解决，同时需要考虑进位的情况。具体思路如下：

1. 创建一个虚拟头节点 dummyHead，用于存储结果链表的头部。
2. 使用指针 current 来追踪当前结果链表的节点，初始指向 dummyHead。
3. 初始化进位值 carry 为 0。
4. 从两个输入链表的头节点开始，分别用指针 l1 和 l2 遍历。
5. 在每次迭代中，将当前节点的值相加，同时加上前一位的进位值。
6. 计算当前位的数字和新的进位值，并将结果作为新节点添加到结果链表中。
7. 移动指针 current 到新创建的节点。
8. 移动指针 l1 和 l2 到它们的下一个节点，继续迭代。
9. 如果遍历结束后仍然有进位值，将进位值作为新节点添加到结果链表的末尾。

代码实现：

以下是使用 Java 实现的 "两数相加" 算法的示例代码：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }
        
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        
        return dummyHead.next;
    }
}

算法分析：

• 时间复杂度：由于遍历两个链表一次，时间复杂度为 O(max(n, m))，其中 n 和 m 分别是两个链表的长度。
• 空间复杂度：除了结果链表外，只需要常数级别的额外空间，因此空间复杂度为 O(1)。

示例和测试：

假设有两个链表分别表示数字 342 和 465，它们逆序存储如下：

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4

根据算法，将两个数字相加得到 807，以链表的形式返回结果：

public class Main {
    public static void main(String[] args) {
        AddTwoNumbers solution = new AddTwoNumbers();
        
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        
        ListNode result = solution.addTwoNumbers(l1, l2);
        
        // 输出结果
        while (result != null) {
            System.out.print(result.val + " -> ");
            result = result.next;
        }
    }
}

总结：

"两数相加" 算法问题涵盖了链表的遍历、数学运算和进位处理，是一个经典的链表操作题目。通过实现该算法，我们可以更深入地理解链表操作的核心思想，同时为处理类似的数学运算问题提供了有用的方法。