你的位置:首页 > Java教程

[Java教程]【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.

解题思路

这道题目比较简单,设置一个变量保存进位便能得到答案。唯一需要注意的一点是考虑两个链表的长度的情况。还有特别要考虑类似1+9999=10000这样的情况:也就是说,即使一个链表已经遍历完毕,进位与另一个链表对应位置数字相加仍有可能产生进位。

代码如下:

public class Solution {  public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {		if(l1==null)			return l2;		if(l2==null)			return l1;		int len1 = getLength(l1);		int len2 = getLength(l2);		//保证l1链表的长度不小于l2		if(len1<len2){			ListNode l=l1;			l1=l2;			l2=l;		}				int p=0; //用来保存进位		int n=l1.val+l2.val;		p=n/10;		n=n%10;		ListNode head = new ListNode(n);		ListNode current = head;		l1=l1.next;		l2=l2.next;		//还没有扫描完l2的情况		while(l2!=null){			n=l1.val+l2.val+p;			p=n/10;			n=n%10;			ListNode node = new ListNode(n);			current.next=node;			current=node;			l1=l1.next;			l2=l2.next;		}		//扫描完l2的情况		while(l1!=null){			n=l1.val+p;			p=n/10;			n=n%10;			ListNode node = new ListNode(n);			current.next=node;			current=node;			l1=l1.next;		}		//最后是否需要进位		if(p==1){			ListNode node = new ListNode(1);			current.next=node;		}    return head;  }	public static int getLength(ListNode l){		int count=0;		while(l!=null){			count++;			l=l.next;		}		return count;	}}