从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账号...