LintCode 167 · Add Two Numbers.java

	/**
	* Definition for ListNode
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	// Approach #1 - T O(max(n, m)) - S O(1)
	public class Solution {
	/**
	* @param l1: the first list
	* @param l2: the second list
	* @return: the sum list of l1 and l2
	*/
	public ListNode addLists(ListNode l1, ListNode l2) {
	// handle corner cases
	if (l1 == null) {
	return l2;
	}
	if (l2 == null) {
	return l1;
	}
	// create a new list for result
	ListNode dummyPreHead = new ListNode(-1);
	ListNode tail = dummyPreHead;
	ListNode left = l1;
	ListNode right = l2;
	int carry = 0;
	while (left != null || right != null) {
	int number = ((left == null) ? 0 : left.val) + ((right == null) ? 0 : right.val) + carry;
	carry = (number > 9) ? 1 : 0;
	number = (number > 9) ? number - 10 : number;
	tail.next = new ListNode(number);
	tail = tail.next;
	if (left != null) {
	left = left.next;
	}
	if (right != null) {
	right = right.next;
	}
	}
	if (carry > 0) {
	tail.next = new ListNode(carry);
	}
	return dummyPreHead.next;
	}
	}

view raw LintCode 167 · Add Two Numbers.java hosted with ❤ by GitHub