当前位置:网站首页>牛客每日刷题之链表
牛客每日刷题之链表
2022-08-09 05:38:00 【_18shou】
作者简介:我是18shou,一名即将秋招的java实习生
个人主页:_18shou
系列专栏:牛客刷题专栏
推荐一款模拟面试、刷题神器 在线刷题面经模拟面试
目录
题目
链表相加(二)
假设链表中每一个节点的值都在0-9之间, 那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
数据范围:0≤n,m<1000000,链表任意值0<val<9
要求:空间复杂度0(n),时间复杂度0(n)
例如:链表1为9->3->7,链表2为6->3,最后生成新的结果链表为1->0->0->0.
思路
假设链表中每一个节 点的值都在0-9之间,那么链表整体就可以代表一个整数。
我们知道题目已经限定了每个节点的值都不为负数了,所以我们就可以不考虑符号的问题了,那么就很简单了。
我们先看- - :下题目给的例子: .
例如:链表1为9->3->7,链表2为6->3,最后生成新的结果链表为1->0->0->0.
从这个例子我们可以得到:
1、两个链表的长度可能不等,需要对齐
2、相加后可能需要进位
对齐进位
因为我们无法保证两个链表长度一致, 所以我们干脆从后往前对齐,跟我们整数再做加法一样
题解
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// 进行判空处理
if(head1 == null)
return head2;
if(head2 == null){
return head1;
}
// 反转h1链表
head1 = reverse(head1);
// 反转h2链表
head2 = reverse(head2);
// 创建新的链表头节点
ListNode head = new ListNode(-1);
ListNode nHead = head;
// 记录进位的数值
int tmp = 0;
while(head1 != null || head2 != null){
// val用来累加此时的数值(加数+加数+上一位的进位=当前总的数值)
int val = tmp;
// 当节点不为空的时候,则需要加上当前节点的值
if (head1 != null) {
val += head1.val;
head1 = head1.next;
}
// 当节点不为空的时候,则需要加上当前节点的值
if (head2 != null) {
val += head2.val;
head2 = head2.next;
}
// 求出进位
tmp = val/10;
// 进位后剩下的数值即为当前节点的数值
nHead.next = new ListNode(val%10);
// 下一个节点
nHead = nHead.next;
}
// 最后当两条链表都加完的时候,进位不为0的时候,则需要再加上这个进位
if(tmp > 0){
nHead.next = new ListNode(tmp);
}
// 重新反转回来返回
return reverse(head.next);
}
// 反转链表
ListNode reverse(ListNode head){
if(head == null)
return head;
ListNode cur = head;
ListNode node = null;
while(cur != null){
ListNode tail = cur.next;
cur.next = node;
node = cur;
cur = tail;
}
return node;
}
}
复杂度
空间复杂度O(n),时间复杂度0(n)
结语
兄弟们,一起来刷题嘎嘎的写题
边栏推荐
猜你喜欢
随机推荐
NFT协议OMNI因重入攻击损失1300ETH
A day to learn a public company: Sophia
第三章搜索与图论(一)
22-08-08 西安 尚医通(04)MongoDB命令、MongoTemplate、MongoRepository
What is it like to work at Kuaishou?
MOS管的选型
2022牛客多校联赛第七场 题解
剑指Offer-二维动态规划问题题目总结
STM32Cube学习笔记(delay)
MATLAB图像处理入门
查询的结果封装到实体类中并使用集合储存
找两个单身狗
【mysql数据库】mysql数据库的使用
JVM:(六)运行时数据区之本地方法栈
【计算机网络-哈工大】---学习笔记(下)---(一)网络安全、密码学基础、对称、公钥、身份认证、数字签名、KDC\CA
TP6的安装与测试
Transaction rolled back because it has been marked as rollback-only
浅谈单片机Boot的几种自刷新方式
【过一下18】超参数优化
P8462 「REOI-1」奶油蛋糕