每日小记-长短链表遍历,规则统一
在同时遍历两条链的时候,由于链表的长度不一,可能造成一条链先遍历完成,另一条长链单独处理的情况
如:
合并有序链表
但是有些情况下,在短链遍历完成之后,可以继续假设短链的数据,使得操作统一
比如:链表加法
2. 两数相加
给你两个非空 的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0开头。
此题中,低位运算完成后,长链的高位单独计算,需要考虑各种进位的情况
不如假设短链的高位全是0,这样就统一了计算规则
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head=new ListNode(0,null),p=head;//头结点,尾插法控制指针
int flag=0;//进位
while(l1!=null||l2!=null){//注意判断不是&了
int v1=l1==null?0:l1.val;//短链的高位设置为0
int v2=l2==null?0:l2.val;
int val=(v1+v2+flag);
flag=val/10;
p.next=new ListNode(val%10,null);
p=p.next;
//长链指针后移,短链为null不动
if(l1!=null)
l1=l1.next;
if(l2!=null)
l2=l2.next;
}
if(flag==1)//处理最高位的进位
p.next=new ListNode(flag,null);
return head.next;//返回值去掉头结点
}