做汽车价格的网站,梧州论坛社区,郑州网红,c2c模式是什么不能简单认为将两条链表转变为整数后进行运算#xff0c;然后将结果转变为链表。因为如果链表很长#xff0c;这可能会导致整数溢出。 在正常的两个整数加法运算时#xff0c;我们是从低位开始#xff0c;然后依次相加更高位的数字#xff0c;所以不难想到我们需要将链表反… 不能简单认为将两条链表转变为整数后进行运算然后将结果转变为链表。因为如果链表很长这可能会导致整数溢出。 在正常的两个整数加法运算时我们是从低位开始然后依次相加更高位的数字所以不难想到我们需要将链表反转方便我们从原链表的尾节点开始遍历到头节点。另外还要考虑运算时产生的进位。 public ListNode addTwoNumbers(ListNode head1, ListNode head2) {// 反转输入链表使得数字的相加从低位到高位进行head1 reverseList(head1);head2 reverseList(head2);// 调用 addReversed 方法进行相加操作ListNode reversedHead addReversed(head1, head2);// 最后再次反转得到的链表得到最终相加的结果return reverseList(reversedHead);}// 反转链表private ListNode reverseList(ListNode head) {ListNode prev null;ListNode cur head;while (cur ! null) {ListNode next cur.next;cur.next prev;prev cur;cur next;}return prev;}// 将两个反转后的链表相加private ListNode addReversed(ListNode head1, ListNode head2) {ListNode dummy new ListNode(0);ListNode sumNode dummy;int carry 0;// 循环遍历两个链表的每一位while (head1 ! null || head2 ! null) {// 获取当前位的值若为空则取0int sum (head1 null ? 0 : head1.val) (head2 null ? 0 : head2.val) carry;// 计算是否有进位carry sum 10 ? 1 : 0;// 若有进位更新当前位的值sum sum 10 ? sum - 10 : sum;// 创建新节点存储当前位的和连接到相加后的链表ListNode newNode new ListNode(sum);sumNode.next newNode;sumNode sumNode.next;// 移动到下一位head1 head1 null ? null : head1.next;head2 head2 null ? null : head2.next;}// 如果循环结束后仍有进位增加一个新节点存储进位if (carry 0) {sumNode.next new ListNode(carry);}// 返回相加后的链表头节点return dummy.next;}
