菜鸟的算法入门：java的链表操作
2021-07-08 20:05
标签：示例 while 自身 flag 除了 菜鸟 div add 刷题 从C语言的指针开始，我的算法之路就结束了！ 今天为了找个好的实习，不得不捡起来，写了三年的web，算法落下了太多了 今天在leetcode上刷题，难在了一个简单的链表上，因此记录一下 解题过程是几经波折的，最开始弄出来的答案还是头插式的，并且还超时了，真菜 在本题中，采用的是尾插法，不停的在链表的尾部插入新的节点 取值时，只需要对最开始的head进行向下取值即可 菜鸟的算法入门：java的链表操作 标签：示例 while 自身 flag 除了 菜鸟 div add 刷题 原文地址：https://www.cnblogs.com/fdzang/p/9581687.html题目：给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 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;
}
}输入：(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）
重复这项工作
下一篇：Python中的函数