leetcode实践：通过链表存储两数之和
2024-08-24 17:03:14
- 题目：
两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
- 示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
- 代码实现：
public class AddTwoNumbers {
/**
* 思路：实现链表与long数值的互转
* 失败：链表结构太长超过long值无法转换
* @param l1 ListNode
* @param l2 ListNode
* @return ListNode
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
long m = 0, mIndex = 0;
long n = 0, nIndex = 0;
while(true) {
Double d = Math.pow(10, mIndex);
m += l1.val * d.longValue();
if(l1.next != null) {
l1 = l1.next;
mIndex++;
} else {
break;
}
}
while(true) {
Double d = Math.pow(10, nIndex);
n += l2.val * d.longValue();
if(l2.next != null) {
l2 = l2.next;
nIndex++;
} else {
break;
}
}
return ListNode.buildFromNumber(m + n);
}
/**
* 思路：每一个节点进行相加，如果有进位，则给下一节点额外加1
* @param l1 ListNode
* @param l2 ListNode
*/
public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
ListNode p1 = l1;
ListNode p2 = l2;
ListNode head = new ListNode(0);
ListNode curr = head;
int bit = 0;
while(p1 != null || p2 != null) {
int x = p1 == null ? 0 : p1.val;
int y = p2 == null ? 0 : p2.val;
int sum = x + y + bit;
if (sum >= 10) {
sum = sum % 10;
bit = 1;
} else {
bit = 0;
}
curr.next = new ListNode(sum);
curr = curr.next;
p1 = p1 == null ? null : p1.next;
p2 = p2 == null ? null : p2.next;
}
if(bit > 0) {
curr.next = new ListNode(bit);
}
return head.next;
}
public static void main(String[] args) {
int[] n1 = {9};
int[] n2 = {1,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9};
ListNode l1 = ListNode.buildFromArray(n1);
ListNode l2 = ListNode.buildFromArray(n2);
System.out.println(l1.dump());
System.out.println(l2.dump());
AddTwoNumbers addTwoNumbers = new AddTwoNumbers();
ListNode l3 = addTwoNumbers.addTwoNumbers2(l1, l2);
System.out.println(l3.dump());
}
public static void main2(String[] args) {
long n1 = 9L;
long n2 = 999999999999999991L;
ListNode l1 = ListNode.buildFromNumber(n1);
ListNode l2 = ListNode.buildFromNumber(n2);
System.out.println(l1.dump());
System.out.println(l2.dump());
AddTwoNumbers addTwoNumbers = new AddTwoNumbers();
ListNode l3 = addTwoNumbers.addTwoNumbers(l1, l2);
System.out.println(l3.dump());
}
}
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
public String dump() {
StringBuilder out = new StringBuilder();
out.append(val);
ListNode nextNode = this.next;
while(nextNode != null) {
out.append(" -> ").append(nextNode.val);
nextNode = nextNode.next;
}
return out.toString();
}
public static ListNode buildFromArray(int[] arr) {
ListNode head = new ListNode(0);
ListNode curr = head;
for (int a : arr) {
curr.next = new ListNode(a);
curr = curr.next;
}
return head.next;
}
public static ListNode buildFromNumber(long num) {
ListNode head = new ListNode(0);
ListNode curr = head;
int sumIndex = 1;
while(true) {
Double d = Math.pow(10, sumIndex);
long bitVal = num % d.longValue();
long val = bitVal / (d.longValue() / 10);
curr.next = new ListNode((int)val);
curr = curr.next;
sumIndex++;
num -= bitVal;
if (num <= 0) {
break;
}
}
return head.next;
}
}
最新文章
- Linux：JDK配置
- [DP]数位DP总结
- 调用WCF Data Service的几点Tips
- 在VS2010中使用附加进程的方式调试IIS中的页面
- centos install shutter (How to enable Nux Dextop repository on CentOS or RHEL)
- PHP漏洞全解(四)-xss跨站脚本攻击
- 在WinForm中使用委托来在其他线程中改变控件的显示
- VLD 1.0 ReadMe翻译尝试
- 常用Java片段
- iOS RunTime你知道了总得用一下
- vuejs子组件向父组件传递数据
- kafka分布式消息队列介绍以及集群安装
- 22. leetcode 242. Valid Anagram(由颠倒字母顺序而构成的字)
- C#基础(六）--枚举的一些常用操作
- PyCharm链接服务器同步代码
- python3 分布式爬虫
- Beta冲刺 （2/7）
- Golang中的自动伸缩和自防御设计
- mysql 将行拼接成字符串的方法
- 算法面经之讯飞+CVTE