题解 | #链表相加(二)#
链表相加(二)
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
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 相加,计算和以及新的进位。然后我们创建一个新的节点,保存和的个位数,并将其添加到结果链表的末尾。然后我们移动链表的指针和结果链表的指针。在遍历结束后,我们还需要检查最后是否还有进位,如果有,还需要在结果链表的末尾添加一个节点。
最后,我们需要再次反转结果链表,使其与输入的链表同方向,然后返回结果链表的头节点。