5.链表逆序存放两个数求和

客官°小女子只卖身不卖艺 2022-03-14 10:12 156阅读 0赞

/**
     * 两个链表存放着数字：1->2->3+1->4->5=2->6->8 321+541=862
     * 1->2->3+1->4=2->6->3  321+41=362
     * @author CL
     *
     */
    public class LinkListAddNums {
    
    	    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	    	//初始化结果链表
    	        ListNode head = new ListNode(0);
    	        head.next=null;
    	        //t:当前链表的头节点，pre:head的前一个结点
    	        ListNode t = head,pre=null; 
    	        while(l1!=null||l2!=null){
    	        	//val：计算两个链表对应的位置的数的和
    	            int val =0;
    	            if(l1!=null&&l2!=null){
    	                 val = l1.val+l2.val;
    	                 l2=l2.next;
    	                 l1=l1.next;
    	            }else{
    	                if(l1==null){
    	                	//l1没有节点了，val=l2的值
    	                    val=l2.val;
    	                    l2=l2.next;
    	                }else{
    	                	//同理
    	                     val=l1.val;
    	                     l1=l1.next;
    	                }
    	            }
    	            //无论有没有进位都要new一个后继结点，最后最高为如果没有进位的话要处理（去除最后一个结点）
    	            //建立后继结点，后继节点值为（当前结点的值+val）的进位部分
    	            head.next=new ListNode((val+head.val)/10);
    	            //当前结点的值是：（当前结点的值+val）的个位部分
    	            head.val=(val+head.val)%10;  
    	            //保存前一个结点，head指向当前结点
    	            pre=head;
    	            head=head.next;
    	        }
    	        //如果最终的进位为0，把最后的结点去掉
    	        if(head.val==0){
    	        	pre.next=null;
    	        }
    	        return t;
    	    }
    	    
    	    public static void main(String[] args) {
    			ListNode l1= new ListNode(1);
    			ListNode l2= new ListNode(8);
    			ListNode l3= new ListNode(3);
    			l1.next=l2;
    			l2.next=null;
    			ListNode l4= new ListNode(0);
    			ListNode l5= new ListNode(9);
    			ListNode l6= new ListNode(4);
    			l4.next=null;
    			l5.next=null;
    			l6.next=null;
    			ListNode re=addTwoNumbers(l1, l4);
    			while(re!=null){
    				System.out.print(re.val+"-->");
    				re=re.next;
    			}
    		}
    }