LeetCode 开刷2 ADD Two Numbers

趁着还有热情，接着刷。

题目：

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:7 -> 0 -> 8

题目意思大概就是把2个整数表示成倒叙的链表，然后加起来。

最开始写的时候以为java和C++似的，链表用->来表示下一个。

后来才注意到题目中给出了链表类的定义，果然改不了粗心的毛病。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

解题：1

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null)
            return l2;
        if(l2 == null )
            return l1;
        ListNode result = null;//新链表的头结点
        ListNode sum = null;//指向尾节点
        int ge = 0;//因为只有2个一位数相加，所以涉及到进位，一个保存个位，一个保存十位
        int shi = 0;
        
        while(l1!=null||l2!=null)
        {
            ge = shi;//当前各位的刚才进的十位
            if(l1!=null)
            {
                ge +=l1.val;
            }
            if(l2!=null)
            {
                ge +=l2.val;
            }
            shi = ge / 10;
            ge = ge % 10;
            if(sum == null)//链表为空，新节点为首节点
            {
                sum = new ListNode(ge);
                result = sum;
            }
            else 
            {
                sum.next = new ListNode(ge);
                sum = sum.next;
            }
            if(l1!=null)
                l1 = l1.next;
            if(l2!=null)
                l2 = l2.next;           
        }
        if(shi !=0)//如果还有进位
            sum.next = new ListNode(shi);  
        return result;    
    }

大致思路就是每次去当前节点和上一次的进位加起来，然后有进位的话就进，没有的话就直接作为新节点放在result里面。

代码：2

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null)
            return l2;
        if(l2 == null )
            return l1;
        ListNode result = null;//新链表的头结点
        ListNode sum = null;//指向尾节点
        int ge = 0;//因为只有2个一位数相加，所以涉及到进位，一个保存个位，一个保存十位
        int shi = 0;
        
        while(l1!=null&&l2!=null)
        {
            ge = shi;//当前各位的刚才进的十位
            ge +=l1.val;
            ge+=l2.val;
            shi = ge / 10;
            ge = ge % 10;
            if(sum == null)//链表为空，新节点为首节点
            {
                sum = new ListNode(ge);
                result = sum;
            }
            else 
            {
                sum.next = new ListNode(ge);
                sum = sum.next;
            }
            l1 = l1.next;
            l2 = l2.next;
            
        }
        if(l1==null)
        {
            while(l2!=null){
                ge = shi + l2.val;
                shi = ge /10;
                ge = ge % 10;                
                sum.next = new ListNode(ge);
                sum = sum.next;
                l2 = l2.next;
            }
            
        }
        else if(l2==null)
        {
            
            while(l1!=null)
            {
                ge = shi + l1.val;
                shi = ge /10;
                ge = ge % 10;                
                sum.next = new ListNode(ge);
                sum = sum.next;
                l1 = l1.next;
            }
        }
        if(shi !=0)//如果还有进位
            sum.next = new ListNode(shi);  
        return result;    
    }
	 public static void main(String[] args) {
		
		ListNode l1 = new ListNode(1);
		ListNode l2 = new ListNode(9);
		l2.next = new ListNode(9);
		ListNode result = addTwoNumbers(l1,l2);

	}

感觉还有一种投机取巧的写法。我先试试。写好了的话，补上来。

代码3：

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       
        if(l1 == null)
            return l1;
        if(l2 == null )
            return l2;
        ListNode result = null;//新链表的头结点
        ListNode sum = null;//指向尾节点
        int count = 0;
        int firstNum = 0;
        int SecondNum = 0;
        while(l1!=null)
        {
        	firstNum += l1.val*Math.pow(10, count++);   
        	l1 = l1.next;
        }
        count = 0;
        while(l2!=null)
        {
        	SecondNum += l2.val*Math.pow(10, count++);
        	l2 = l2.next;
        }
        int ResultNum = firstNum+SecondNum;
        System.out.println(ResultNum);
        if(sum == null)
        {
        	sum = new ListNode(ResultNum%10);
        	ResultNum /=10;
        	result = sum;
        }
        while(ResultNum!=0)
        {
        	sum.next = new ListNode(ResultNum%10);
        	ResultNum /= 10;
        	sum = sum.next;
        }
        
        return result;
    }

无奈会越界， 所以pass了。