首页 > 代码库 > Leetcode2--->链表中对应位相加(进位)
Leetcode2--->链表中对应位相加(进位)
题目:
给定两个单链表,单链表中的数都是非负数。链表中的数字都是反向存储的,,每个节点都是个位数,将链表对应的位相加,返回最终的结果;
举例:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
解题思路:
其本质是将链表1和链表2反转之后,对应位相加且进位,结果进行反转,比如上述例子中:342+465 = 807;但由于链表是单链表,不能从后往前遍历,因此可以转换为从前向后加,向后进位,即243+564=708;下面列出解题的几个关键点:
1. 代码中是将链表2加到链表1上的,因此需要注意当链表1比较短的情况,需要使用链表1的最后一个节点链接链表2;
2. 最后一次需要进位时,要扩展节点的情况;比如243 + 567 = 7011;
代码如下:
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution {10 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // l1与l2对应位的值相加,向后进位11 if(l1 == null || l2 == null)12 return null;13 ListNode node1 = l1;14 ListNode node2 = l2;15 ListNode prev = null;16 int jinwei = 0; // 进位17 while(node1 != null){18 node1.val += jinwei;19 if(node2 != null){20 node1.val = node2.val + node1.val;21 node2 = node2.next; 22 }23 jinwei = node1.val / 10;24 node1.val = node1.val % 10;25 prev = node1;26 node1 = node1.next;27 }28 while(node2 != null){ // 链表1比较短的情况29 node2.val += jinwei;30 jinwei = node2.val / 10;31 node2.val = node2.val % 10;32 prev.next = node2;33 node2 = node2.next;34 prev = prev.next;35 }36 if(jinwei > 0) // 最后还要进一位37 prev.next = new ListNode(jinwei);38 return l1;39 }40 }
Leetcode2--->链表中对应位相加(进位)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。