菜鸟的算法入门:java的链表操作

菜鸟的算法入门:java的链表操作

从C语言的指针开始,我的算法之路就结束了!

今天为了找个好的实习,不得不捡起来,写了三年的web,算法落下了太多了

今天在leetcode上刷题,难在了一个简单的链表上,因此记录一下

题目:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。    你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例: 输入:(
2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807

解题过程是几经波折的,最开始弄出来的答案还是头插式的,并且还超时了,真菜

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int flag=0;//用于判断是否进位  1为进位,0为不进,可以直接做数值存储
     int sum=0; //用于存放当前位相加的和 int i1=0;  //l1的val int i2=0;  //l2的val ListNode head=new ListNode(0); //声明一个节点为头节点,因为是尾插,最终的node为最后一个节点的节点值 ListNode node=head;  //声明一个临时变量,用于尾插的操作 while(l1!=null||l2!=null){
       //如果当前节点为空,则赋值为0,方便继续运算
il = (l1 !=null) ? l1.val : 0;if(l2!=null){ i2=l2.val; }else{ i2=0; } sum=i1+i2+flag; //得到当前运算的和 flag=sum/10;  //是否进位

       //对当前节点尾插一个节点,存储当前节点的值 第一次运算时,相当于head.next=new ListNode(7) 这也是为什么最后返回head.next的原因 node.next
=new ListNode(sum%10);
       //将当前节点的next赋值给当前节点,即将指针移到链表的尾部 node
=node.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; }
     //如果最后又进位,再给尾部插入一个新的节点
if (flag > 0) { node.next = new ListNode(flag); } return head.next; } }

在本题中,采用的是尾插法,不停的在链表的尾部插入新的节点

取值时,只需要对最开始的head进行向下取值即可

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

0.开始循环之前

head={
    val : 0
    next : null
}
node={
    val : 0
    next : null
}

1.第一次循环

node.next=new ListNode(sum%10); 运行结果:
node={
    val : 0
    next : {
        val : 7
        next : null
    }
}
由于head=node:
head={
    val : 0
    next : {
        val : 7
        next : null
    }
}
node=node.next; 运行结果:
node={
    val : 7
    next : null;
}

head不变

2.第二次循环

node.next=new ListNode(sum%10); 运行结果:
node={
    val : 7
    next : {
        val : 0
        next : null
    }
}
由于head=node:
head={
    val : 0
    next : {
        val : 7
        next : {
            val : 0
            next : null
        }
    }
}
node=node.next; 运行结果:
node={
    val : 0
    next : null;
}

head不变    

3.第三次循环

node.next=new ListNode(sum%10); 运行结果:
node={
    val : 0
    next : {
        val : 8
        next : null
    }
}
由于head=node:
head={
    val : 0
    next : {
        val : 7
        next : {
            val : 0
            next : {
                val : 8
                next : null
            }
        }
    }
}
node=node.next; 运行结果:
node={
    val : 8
    next : null;
}

head不变          

4.返回结果

head={
    val : 0
    next : {
        val : 7
        next : {
            val : 0
            next : {
                val : 8
                next : null
            }
        }
    }
}

head.next={
    val : 7
    next : {
        val : 0
        next : {
            val : 8
            next : null
        }
    }
} 

5.总结

最开始的head节点是整个运算中不动的,node节点相当于其的一个尾巴,
不断的添加数据到自身,然后后移到添加的节点上去

类似于一个贪吃蛇,head节点一直不变,node节点是一个工作节点(长度为1)
  他的工作是找到一个新的节点,让其附着在自己的next上(node.next=new ListNode)
  然后移到到这个新的节点上去(node=node.next)
  重复这项工作

转载于:https://www.cnblogs.com/fdzang/p/9581687.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101454.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • type=INNODB和engine=INNODB的区别

    type=INNODB和engine=INNODB的区别

  • pycharm svn设置_新手配置交换机详细教程

    pycharm svn设置_新手配置交换机详细教程1.打开pycharm设置配置svn.exe的地址Seting-versioncontrol-subversion按照红色填入svn.exe的路径2.在配置的时候找不到svn.exe的方法原因是在默认安装svn的时候忽略了安装svn.exe2.1在卸载或更改程序中重新安装一下svn2.2按照图片进行操作完成后需要重新打开pycharm设置,就可以找到svn.exe3.配置自动化脚本svn的地址导出的时候可以选择放置的位置如D盘4.注意事项pycharm的使用和本地使用没有太

  • datatable删除行

    先列出正确的写法,如果你只想马上改错就先复制吧,如果你有时间想学习一下就继续看下面列出可能出错的可能性吧。1.如果只是想删除datatable中的一行,可以用DataRow的delete,但是必须

    2021年12月24日
  • JavaFX Script语言教程「建议收藏」

    JavaFX Script语言教程「建议收藏」JavaFXScript™(下文中称为JavaFX)语言是一种声明式的静态类型编程语言。它具有第一级函数(first-classfunctions)、声明式的语法、列表推导(list-comprehensions)及基于依赖关系的增量式求值(incrementaldependency-basedevaluation)等特征。JavaFX脚本式语言特别适用于Java2Dswi…

  • matlab如何随机选颜色,Matlab 画图修饰-随机线条和随机颜色

    matlab如何随机选颜色,Matlab 画图修饰-随机线条和随机颜色转载自:http://www.zhaoyanpeng.cn/archives/237当需要对同一曲线不同参数下进行模拟时需要不同的颜色来加以区分:上例根据RGB颜色,来实现不同颜色曲线的组合,考虑到matlab画图中,颜色分量是以1/255的步长变化的,但是相邻颜色过于接近,因此我们可以选取rand随机数的形式,来实现颜色的随机变化;延伸:MATLAB有一个叫颜色映象的数据结构来代表颜色值。颜色映…

  • 构造函数隐式转换_构造函数实例化对象

    构造函数隐式转换_构造函数实例化对象转载博客:http://blog.csdn.net/thefutureisour/article/details/7705771构造函数隐式转换构造函数会引起一个不引人注意的问题:用单个实参来调用的构造函数定义了从从形参类型到类类型的一个隐式转换。举个例子说:classSales_item{public:std::istream&input(std…

    2022年10月11日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号