题意: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 return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
【Leetcode445】思路一:两个链表分别反转,相加后,再反转,思路直接,但题目不允许
思路二:不反转,先统计两个链表长度,相等长度的低位段相加,向高位进位。
比价而言,方法二稍快,但是技巧复杂,容易出错。
其实我认为程序设计的关键在于能通过case的情况下,节约应试者的时间,且易于维护扩展。
方法二代码:
private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int len1 = 0;
int len2 = 0;
ListNode temp1 = l1;
ListNode temp2 = l2;
while (temp1 != null) {
len1++;
temp1 = temp1.next;
}
while (temp2 != null) {
len2++;
temp2 = temp2.next;
}ListNode head = new ListNode(0);
ListNode temp = head;
temp.next = recur(l1, l2, len1, len2);
if (temp.next.val >= 10) {
temp.next.val = temp.next.val % 10;
temp.val = 1;
return head;
} else {
return head.next;
}
}
//返回两个链表相加后的头部。
public static ListNode recur(ListNode l1, ListNode l2, int len1, int len2)
{
if (l1 == null && l2 == null) {
return null;
}ListNode l;
ListNode next;
int val;
if (len1 == len2) {
next = recur(l1.next, l2.next, len1 - 1, len2 - 1);
val = l1.val + l2.val;
} else if (len1 > len2) {//链表1比较长
next = recur(l1.next, l2, len1 - 1, len2);
val = l1.val;
} else {//链表2比较长
next = recur(l1, l2.next, len1, len2 - 1);
val = l2.val;
}
if (next != null && next.val >= 10) {
next.val = next.val % 10;
val++;
}
l = new ListNode(val);
l.next = next;
return l;
}
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点(详细介绍 Python 中的 7 种交叉验证方法!)
- 网络|简单聊聊压缩网络