摘要：感想刚开始看到这道题，觉得很简单，跟归并的过程比较像，算法复杂度。可以半小时之内完全可以搞定。可是随着一次次提交出问题，发现似乎没有我想的那么简单问题其实就出现在各种没有处理好，剑指多次提到的写代码要注意健壮性深刻体会到了。
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
感想： 刚开始看到这道题，觉得很简单，跟归并merge的过程比较像，算法复杂度O（n）。可以半小时之内完全可以搞定。可是随着一次次提交出问题，发现似乎没有我想的那么简单...问题其实就出现在各种corner cases没有处理好，which is also 剑指offer多次提到的写代码要注意健壮性....深刻体会到了。
思路： 处理好进位，要自己手动写各种情况的测试用例，确保程序的健壮性...
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
private int getSum(int x, int y, int digit){
int value = x+y+digit;
if(value>=10)
return value-10;
else
return value;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = l1;
ListNode q = l2;
// new head node for the resultlist
ListNode newHead = new ListNode(getSum(p.val,q.val,0));
ListNode pHead = newHead;
int digit;//处理进位
if(p.val+q.val-10 >= 0){
digit = 1;
}
else
digit = 0;
p = p.next;
q = q.next;
while(p!=null || q != null){
// 两个链表长度相等时候的处理
if(p!=null &&q!=null){
ListNode temp = new ListNode(getSum(p.val, q.val,digit));
pHead.next = temp;
pHead = pHead.next;
if(p.val+q.val+digit-10 >= 0){
digit = 1;
}
else
digit = 0;
p = p.next;
q = q.next;
}
// 两个链表长度不等时候的处理
else if(p==null){
ListNode temp = new ListNode(getSum(0, q.val,digit));
pHead.next = temp;
pHead = pHead.next;
if(0+q.val-10+digit >= 0){
digit = 1;
}
else{
digit = 0;
}
q = q.next;
}
// 两个链表长度不等时候的处理
else if(q==null){
ListNode temp = new ListNode(getSum(p.val, 0,digit));
pHead.next = temp;
pHead = pHead.next;
if(0+p.val-10+digit >= 0){
digit = 1;
}
else{
digit= 0;
}
p = p.next;
}
}
// 链表1： 5 链表2： 5 这个时候的处理
if(digit ==1){
ListNode temp = new ListNode(getSum(0, 0,digit));
pHead.next = temp;
}
return newHead;
}
}
更优美一点的代码
javapublic class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry =0;
ListNode newHead = new ListNode(0);
ListNode p1 = l1, p2 = l2, p3=newHead;
while(p1 != null || p2 != null){
if(p1 != null){
carry += p1.val;
p1 = p1.next;
}
if(p2 != null){
carry += p2.val;
p2 = p2.next;
}
p3.next = new ListNode(carry%10);
p3 = p3.next;
carry /= 10;
}
if(carry==1)
p3.next=new ListNode(1);
return newHead.next;
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64315.html
摘要：难度题目给定两个非空且元素非负的链表。链表中的数字以逆序排列且每个结点只含一个一位数。使两个数相加并反回其结果。思路设置头结点简化操作。从前向后遍历相加。 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse or...
摘要：这题是说给出两个链表每个链表代表一个多位整数个位在前比如代表着求这两个链表代表的整数之和同样以倒序的链表表示难度这个题目就是模拟人手算加法的过程需要记录进位每次把对应位置两个节点如果一个走到头了就只算其中一个的值加上进位值 Add Two Numbers You are given two linked lists representing two non-negative num...
摘要：描述中文解释给定两个非空的链表里面分别包含不等数量的正整数，每一个节点都包含一个正整数，肯能是，但是不会是这种情况。我们需要按照倒序计算他们的和然后再次倒序输出。 描述 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in rev...
Problem You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and ...
摘要：题目要求对以链表形式的两个整数进行累加计算。思路一链表转置链表形式跟非链表形式的最大区别在于我们无法根据下标来访问对应下标的元素。因此这里通过先将链表转置，再从左往右对每一位求和来进行累加。通过栈可以实现先进后出，即读取顺序的转置。 题目要求 You are given two non-empty linked lists representing two non-negative i...
阅读 1893·2021-11-24 11:16
阅读 3257·2021-09-10 10:51
阅读 3179·2021-08-03 14:03
阅读 1261·2019-08-29 17:03
阅读 3238·2019-08-29 12:36
阅读 2218·2019-08-26 14:06
阅读 492·2019-08-23 16:32
阅读 2660·2019-08-23 13:42
