题解 | #链表相加(二)#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 先将两个链表翻转
        head1 = reverseList(head1);
        head2 = reverseList(head2);

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;  // 进位

        // 遍历两个链表，同时计算和
        while (head1 != null || head2 != null || carry != 0) {
            int val1 = head1 != null ? head1.val : 0;
            int val2 = head2 != null ? head2.val : 0;

            int sum = val1 + val2 + carry;
            carry = sum / 10;  // 计算进位

            // 新建节点保存当前位的值
            ListNode newNode = new ListNode(sum % 10);
            curr.next = newNode;
            curr = newNode;

            // 移动指针
            if (head1 != null) {
                head1 = head1.next;
            }
            if (head2 != null) {
                head2 = head2.next;
            }
        }

        // 最后将结果链表翻转并返回
        return reverseList(dummy.next);
    }

    // 翻转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

在这个实现中，我们首先反转了两个输入的链表，然后按位相加生成新的链表。对于每一位，我们需要计算和，并处理可能的进位。我们使用一个变量 carry 来保存进位，初始化为 0。对于两个链表中的每一位，我们分别取出其值（如果对应的链表已经遍历完，则视为 0），然后与 carry 相加，计算和以及新的进位。然后我们创建一个新的节点，保存和的个位数，并将其添加到结果链表的末尾。然后我们移动链表的指针和结果链表的指针。在遍历结束后，我们还需要检查最后是否还有进位，如果有，还需要在结果链表的末尾添加一个节点。

最后，我们需要再次反转结果链表，使其与输入的链表同方向，然后返回结果链表的头节点。